Copy List with Random Pointer

[kokocan12]

Problem

When a root node of Linked List is given, each node has next, random pointer,
deep copy the original Linked List.

None of the deep copied elements points the element of original Linked List.

Approach

Using object dictionary, store matching information of Linked List.
For example, key: Node -> value: Node.
After storing to dictionary, Node.random = dict.get(Node.random).

The code is below.

const copyRandomList = function(head) {
    const dict = new WeakMap();
    const headTemp = head;
    const dummy = new Node(0);
    let current = dummy;
    
    while(head) {
        current.next = new Node(head.val);
        dict.set(head, current.next)
        
        current = current.next;
        head = head.next;
    }
    
    head = headTemp;
    current = dummy.next;
    while(head) {
        current.random = dict.get(head.random);
        
        current = current.next;
        head = head.next;
    }
    
    return dummy.next;
};