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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node. Your code will only be given the head of the original linked list.

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random is null or is pointing to some node in the linked list.

The iterative solution to this problem does not model it as a graph, instead simply treats it as a LinkedList. When we are iterating over the list, we can create new nodes via the random pointer or the next pointer whichever points to a node that doesn't exist in our old --> new dictionary.

Traverse the linked list starting at head of the linked list.

In the above diagram we create a new cloned head node. The cloned node is shown using dashed lines. In the implementation we would even store the reference of this newly created node in a visited dictionary.

Random Pointer

If the random pointer of the current node i points to the a node j and a clone of j already exists in the visited dictionary, we will simply use the cloned node reference from the visited dictionary. If the random pointer of the current node i points to the a node j which has not been created yet, we create a new node corresponding to j and add it to the visited dictionary.

In the above diagram the random pointer of node A points to a node C. Node C which was not visited yet as we can see from the previous diagram. Hence we create a new cloned C ′ node corresponding to node C and add it to visited dictionary.

Next Pointer

If the next pointer of the current node i points to the a node j and a clone of j already exists in the visited dictionary, we will simply use the cloned node reference from the visited dictionary. If the next pointer of the current node i points to the a node j which has not been created yet, we create a new node corresponding to j and add it to the visited dictionary.

In the above diagram the next pointer of node A points to a node B. Node B which was not visited yet as we can see from the previous diagram. Hence we create a new cloned B ′ node corresponding to node B and add it to visited dictionary.

We repeat steps 2 and 3 until we reach the end of the linked list.

In the above diagram, the random pointer of node B points to an already visited node A. Hence in step 2, we don't create a new copy for the clone. Instead we point random pointer of cloned node B ′ to already existing cloned node A ′ .

Also, the next pointer of node B points to an already visited node C. Hence in step 3, we don't create a new copy for the clone. Instead we point next pointer of cloned node B ′ to already existing cloned node C ′ .

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

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
            HashMap<Node,Node> map = new HashMap<>();
    public Node getClonedNode(Node node){
        if(node!=null){
            if(map.containsKey(node)){
                return map.get(node);
            }else{
                map.put(node,new Node(node.val));
                return map.get(node);
            }
        }
        return null;
    }
    public Node copyRandomList(Node head) {
        if(head == null) return null;

        Node firstNode = head;
        Node copyNode = new Node(firstNode.val);
        map.put(firstNode,copyNode);
        while(firstNode!=null){
            copyNode.random = getClonedNode(firstNode.random);
            copyNode.next = getClonedNode(firstNode.next);
            firstNode = firstNode.next;
            copyNode = copyNode.next;
        }
        return map.get(head);

    }
}

Time Complexity : O(N) because we make one pass over the original linked list.

Space Complexity : O(N) as we have a dictionary containing mapping from old list nodes to new list nodes. Since there are N nodes, we have O(N) space complexity.