Problem

Copy List with Random Pointer

Approach

  1. The key point of copying the list with random pointer is how to copy these random pointers in deep copy.
  2. First solution is that we can use a HashMap, making old nodes linked with corresponding new nodes, to record the relationship between old and new nodes.
    • in first loop, we can get a new linked list and every node in the list has correct next pointer, but their random pointers point to null
    • at the same time, we can get the mapping relation: oldNode -> newNode, which is useful for us to get the exact new node.
    • in 2nd loop, we can start from the old head node and new head node. In the go, for every old node, we know which node its’ random pointer points to. and with the help of the mentioned map in first step, we can easily locate which new node is.
  3. Second solution is that we can record the random pointers’ information of old nodes in new nodes and record relation between old and new in the olds. So, Hashmap is no longer needed.
    • in first loop, we need to store random pointers’ information in old nodes into new nodes and store the mapping relation into old nodes.
    • in 2nd loop, we can assign the correct node to new nodes’ random pointer

Code

// approach 1
/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
        Node dummyHead = new Node();
        Node backupDummyHead = dummyHead, backupOldHead = head;
        Map<Node, Node> hash = new HashMap<>();
        while(head != null){
            Node temp = new Node(head.val);
            dummyHead.next = temp;
            dummyHead = dummyHead.next;
            hash.put(head, temp);
            head = head.next;
        }
        head = backupOldHead;
        dummyHead = backupDummyHead.next;
        while(head != null){
            Node curRandom = head.random;
            dummyHead.random = hash.get(curRandom);
            head = head.next;
            dummyHead = dummyHead.next;
        }
        return backupDummyHead.next;
    }
}

// approach 2
/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
        Node dummyHead = new Node();
        Node backupDummyHead = dummyHead, backupOldHead = head;
        while(head != null){
            Node temp = new Node(head.val);
            dummyHead.next = temp;
            temp.random = head.random;
            head.random = temp;
            dummyHead = dummyHead.next;
            head = head.next;
        }
        head = backupOldHead;
        dummyHead = backupDummyHead.next;
        while(head != null){
            if(dummyHead.random != null)
                dummyHead.random = dummyHead.random.random;
            head = head.next;
            dummyHead = dummyHead.next;
        }
        return backupDummyHead.next;
    }
}