Copy List with Random Pointer

Problem Statement

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.

Return the head of the copied linked list.

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

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

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

Approach: Hash Map (Two Passes)

The main challenge in creating a deep copy of a linked list with random pointers is that a random pointer might point to a node that hasn’t been created yet.

To easily solve this, we can use a Hash Map to store the mapping between the original nodes and their corresponding new copied nodes. We can accomplish this in two passes:

1. First Pass (Create Nodes):
   • Initialize a Hash Map (using JavaScript’s Map).
   • Iterate through the original linked list. For every node you encounter, create a brand new node with the same value.
   • Store the mapping in the Hash Map: map.set(originalNode, newNode).
   • Tip: To easily handle null pointers later, you can pre-populate the map with map.set(null, null).
2. Second Pass (Wire Pointers):
   • Iterate through the original linked list a second time.
   • For every original node, retrieve its corresponding new node from the Hash Map: let copy = map.get(curr).
   • Wire the next and random pointers of the new node by looking up the corresponding copied nodes in the Hash Map:
     • copy.next = map.get(curr.next)
     • copy.random = map.get(curr.random)
3. Finally, return the copied head, which is simply map.get(head).

(Note: There is also an $O(1)$ space solution that involves interweaving the copied nodes into the original list, but the Hash Map approach is highly intuitive, standard for this problem, and easily extensible to deep-copying graphs).

Solution

/**
 * // Definition for a _Node.
 * function _Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {_Node} head
 * @return {_Node}
 */
function copyRandomList(head) {
    if (head === null) return null;
    
    // Hash map to store Original Node -> Copied Node
    const map = new Map();
    map.set(null, null); // Handle null pointers gracefully
    
    // 1st Pass: Create all copied nodes and store them in the map
    let curr = head;
    while (curr !== null) {
        const copy = new _Node(curr.val, null, null);
        map.set(curr, copy);
        curr = curr.next;
    }
    
    // 2nd Pass: Wire up the next and random pointers for the copied nodes
    curr = head;
    while (curr !== null) {
        const copy = map.get(curr);
        
        // Lookup the copied versions of the next and random nodes
        copy.next = map.get(curr.next);
        copy.random = map.get(curr.random);
        
        curr = curr.next;
    }
    
    // Return the copied head
    return map.get(head);
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the number of nodes in the linked list. We make exactly two passes over the list. Hash Map insertions and lookups take $O(1)$ time on average.
• Space Complexity: $O(n)$. We use a Hash Map to store a mapping for all $n$ nodes, which takes memory proportional to the size of the linked list.