LeetCode 138. Copy List with Random Pointer

Question

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Explanation

这道题有两种解法。一种用Hashmap存每个节点，然后复制。这种需要占用Extra space。另外一种就是把每个新的节点存到原来的节点的下一个，不用额外空间。

Code

public class Solution {
    // Solution 1: using hashmap and iterate twice. one for nodes, the other for next and random.
    public RandomListNode copyRandomList(RandomListNode head) {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode curr = head;
        // copy the all the nodes and their labels first
        while (curr != null) {
            map.put(curr, new RandomListNode(curr.label));
            curr = curr.next;
        }
        RandomListNode node = head;
        // copy all the next and randoms
        while (node != null) {
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
            node = node.next;
        }
        return map.get(head);
    }

    // Solution 2: no hashmap, only linked list
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        RandomListNode curr = head;
        // copy next
        while (curr != null) {
            RandomListNode newNode = new RandomListNode(curr.label);
            newNode.random = curr.random;
            newNode.next = curr.next;
            curr.next = newNode;
            curr = curr.next.next;
        }
        // copy random
        RandomListNode cur = head;

        while (cur != null) {
            if (cur.next.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        // split list
        RandomListNode newHead = head.next;
        RandomListNode curt = head;
        while (curt != null) {
            RandomListNode tmp= curt.next;
            curt.next = tmp.next;
            curt = curt.next;
            if (tmp.next != null) {
                tmp.next = tmp.next.next;
            }

        }
        return newHead;


    }
}