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.

Example 1:

Input: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1} 
Explanation: Node 1's value is 1, both of its next and random pointer points to Node 2. Node 2's value is 2, its next pointer points to null and its random pointer points to itself. 

Note:

1. You must return the copy of the given head as a reference to the cloned list.

/*
// 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) {
        
    }
}

Idea - 1

If we had a singly linked list, we could keep copying each node as we go along. However the random pointer makes it a little complicated. While making copy of a node we might end up making at most 3 copies: one for the node, one for its next, and the third for its random. Now both next (a previous random pointed to the next) and random (random is pointing to an earlier node) of a node could already have been copied. To retrieve such a copy we keep a map from a node to its copy. The algorithm has time complexity and space complexity .

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null)
        {
            return null;
        }
        
        Node copyHead = new Node(head.val);
        HashMap<Node, Node> map = new HashMap<>();
        map.put(head, copyHead);
        
        Node p = head;
        Node q = copyHead;
        
        while(p != null)
        {
            // invariant: p has already been copied into q
            // we will fix q's next and random here
            
            if(p.next != null)
            {
                Node qnext = map.getOrDefault(p.next, new Node(p.next.val));
                q.next = qnext;
                map.put(p.next, qnext);
            }
            
            if(p.random != null)
            {
                Node qrandom = map.getOrDefault(p.random, new Node(p.random.val));
                q.random = qrandom;
                map.put(p.random, qrandom);
            }
            
            p = p.next;
            q = q.next;
        }
        
        return copyHead;
    }
}


Runtime: 1 ms, faster than 83.25% of Java online submissions for Copy List with Random Pointer.
Memory Usage: 36.8 MB, less than 99.59% of Java online submissions for Copy List with Random Pointer.

Idea - 2

We are using the map to find out where the copy of a given node is. If instead we keep the copy just beside the original node, we do not need the map. We do it in three passes: (1) Make a list of size 2*n where each original node's next will point to its copy and that copy's next will point to the next original node in the original list. (2) We fix random pointer for each copy which is each because the original and copy are adjacent (3) We break the 2*n list into original and copy lists. Time is and space is . Note, we are not counting the size of the out put in space complexity since a deep copy will always require that.

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null)
        {
            return null;
        }
        
        // create 2*n list
        Node p = head;
        while(p != null)
        {
            Node p2 = new Node(p.val);
            Node pnext = p.next;
            p.next = p2;
            p2.next = pnext;
            
            p = pnext;
        }
        
        // fix random pointer of copy
        p = head;
        while(p != null)
        {
            if(p.random != null)
            {
                p.next.random = p.random.next;
            }
            
            p = p.next.next;
        }
        
        Node dummy = new Node(-1);
        Node t = dummy;
        
        // break into two n-size lists
        p = head;
        while(p != null)
        {
            t.next = p.next;
            p.next = p.next.next;
            t = t.next;
            p = p.next;
        }
        
        return dummy.next;
    }
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Copy List with Random Pointer.
Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Copy List with Random Pointer.