Copy List with Random Pointer

LeetCode 138: Copy List with Random Pointer Solution & Explanation

Problem Overview

TL;DR: The optimal solution treats the linked list as a graph and uses a Hash Map during traversal (DFS or BFS) to store the mapping between original nodes and their copies, ensuring every node is cloned exactly once.

In the LeetCode 138 problem, "Copy List with Random Pointer," we are given a linked list where each node contains a standard next pointer and a special random pointer. The random pointer can reference any node in the list or be null. The objective is to create a "deep copy" of this structure. A deep copy means creating entirely new node instances that maintain the exact same topology (connections) as the original list. Modifying the new list should have no effect on the original list.

This is a classic interview question because it tests the ability to handle complex pointer manipulations and data structure mapping.

Brute Force Approach for Copy List with Random Pointer

A naive approach attempts to clone the list in two passes without using a hash map for efficient lookups.

1. First Pass: Iterate through the original list using the next pointers. For every node encountered, create a corresponding new node and link the next pointers correctly. This creates a simple copy of the list structure, ignoring the random pointers initially.
2. Second Pass: Iterate through the new list to set the random pointers. For each node i in the copy, we look at the corresponding node i in the original list to see where its random pointer goes. If original[i].random points to original[j], we must search through the new list to find copy[j] and link it.

Pseudo-code

function copyRandomList(head):
    if head is null return null
    
    // Step 1: Create copy list with only next pointers
    new_head = new Node(head.val)
    curr = head.next
    copy_curr = new_head
    while curr:
        copy_curr.next = new Node(curr.val)
        curr = curr.next
        copy_curr = copy_curr.next
        
    // Step 2: Set random pointers
    curr = head
    copy_curr = new_head
    while curr:
        if curr.random is not null:
            // Find the index of the random target in original list
            target = curr.random
            index = 0
            temp = head
            while temp != target:
                temp = temp.next
                index++
            
            // Find the node at that index in the new list
            target_copy = new_head
            for k from 0 to index:
                target_copy = target_copy.next
            
            copy_curr.random = target_copy
        
        curr = curr.next
        copy_curr = copy_curr.next
        
    return new_head

Analysis

• Time Complexity: $O(N^2)$. For every node (N), finding the target of the random pointer requires scanning the list, which takes $O(N)$ time on average.
• Why it fails: While it might pass very small test cases, the $O(N^2)$ complexity is inefficient for larger inputs ($N=1000$ implies $10^6$ operations, which is borderline but poor practice). More importantly, this approach fails to utilize the structural properties of the data efficiently.

Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)

We will implement this using Depth First Search (DFS) via recursion. This is a clean and intuitive way to traverse the structure.

1. Global Storage: Maintain a Hash Map visited to store the mapping OriginalNode -> CopiedNode.
2. Recursive Function: Define a function clone(node) that takes an original node as input.
3. Base Case: If the input node is null, return null.
4. Memoization Check: Check if node is already in visited. If yes, return visited[node].
5. Node Creation:
   • Create a new node newNode with the value of node.val.
   • Crucial Step: Add node -> newNode to the visited map before making recursive calls. This prevents infinite loops if the list contains cycles (e.g., a node's random pointer points to itself).
6. Recursive Traversal:
   • Set newNode.next = clone(node.next).
   • Set newNode.random = clone(node.random).
7. Return: Return newNode.

Execution Flow

Let's trace the algorithm with a simple example: A -> B, where A.random -> B and B.random -> A.

1. Call clone(A).
2. A is not in map. Create A_copy. Map: {A: A_copy}.
3. Set A_copy.next = clone(A.next) which is clone(B).
   • B is not in map. Create B_copy. Map: {A: A_copy, B: B_copy}.
   • Set B_copy.next = clone(B.next) (null). Returns null.
   • Set B_copy.random = clone(B.random) which is clone(A).
     • A IS in map. Return visited[A] which is A_copy.
   • B_copy.random is now linked to A_copy.
   • Return B_copy.
4. A_copy.next is now linked to B_copy.
5. Set A_copy.random = clone(A.random) which is clone(B).
   • B IS in map. Return visited[B] which is B_copy.
6. A_copy.random is now linked to B_copy.
7. Return A_copy.

The result is a deep copy where A_copy and B_copy are structurally identical to A and B.

Proof of Correctness

The correctness relies on the visited map acting as a definitive source of truth for node identity.

1. Termination: Since there are a finite number of nodes ($N$) and we mark each as visited immediately upon first encounter, the recursion will visit each node exactly once. Cycles are handled by the map check, preventing infinite recursion.
2. Topology Preservation: For every edge $(u, v)$ in the original graph (whether next or random), the algorithm sets the corresponding pointer in the copy to visited[v]. Since visited[v] is the unique deep copy of v, the structure is preserved exactly.

Pattern Reuse Notes

The Graph Traversal (Deep Copy) pattern used in LeetCode 138 is directly applicable to several other popular interview questions:

• LeetCode 133: Clone Graph - The logic is identical. Instead of next and random, you iterate through a list of neighbors.
• LeetCode 1490: Clone N-ary Tree - Same concept applied to a tree structure with variable children.
• LeetCode 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance - While this is a shortest-path problem, understanding graph representation and traversal is the foundational prerequisite.

Mastering the "Hash Map + Recursion" technique for cloning ensures you can handle any deep-copy variation involving cycles or complex references.

Reference Implementation

C++ Solution for LeetCode 138

1/*
2// Definition for a Node.
3class Node {
4public:
5    int val;
6    Node* next;
7    Node* random;
8    
9    Node(int _val) {
10        val = _val;
11        next = NULL;
12        random = NULL;
13    }
14};
15*/
16
17class Solution {
18private:
19    // Hash map to store the mapping from original node to copied node
20    std::unordered_map<Node*, Node*> visited;
21
22public:
23    Node* copyRandomList(Node* head) {
24        // Base case: if the node is null, return null
25        if (head == nullptr) {
26            return nullptr;
27        }
28
29        // If we have already processed this node, return the stored copy
30        if (visited.find(head) != visited.end()) {
31            return visited[head];
32        }
33
34        // Create a new node with the same value
35        Node* newNode = new Node(head->val);
36
37        // Save this node in the map BEFORE recursion to handle cycles
38        visited[head] = newNode;
39
40        // Recursively copy the next and random pointers
41        newNode->next = copyRandomList(head->next);
42        newNode->random = copyRandomList(head->random);
43
44        return newNode;
45    }
46};

Java Solution for LeetCode 138

1/*
2// Definition for a Node.
3class Node {
4    int val;
5    Node next;
6    Node random;
7
8    public Node(int val) {
9        this.val = val;
10        this.next = null;
11        this.random = null;
12    }
13}
14*/
15
16class Solution {
17    // HashMap to keep track of visited nodes to avoid cycles and duplicates
18    private Map<Node, Node> visited = new HashMap<>();
19
20    public Node copyRandomList(Node head) {
21        if (head == null) {
22            return null;
23        }
24
25        // If the node is already cloned, return the reference to the clone
26        if (visited.containsKey(head)) {
27            return visited.get(head);
28        }
29
30        // Create a new node
31        Node newNode = new Node(head.val);
32
33        // Store in map immediately
34        visited.put(head, newNode);
35
36        // Recursively clone next and random pointers
37        newNode.next = copyRandomList(head.next);
38        newNode.random = copyRandomList(head.random);
39
40        return newNode;
41    }
42}

Python Solution for LeetCode 138

1"""
2# Definition for a Node.
3class Node:
4    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
5        self.val = int(x)
6        self.next = next
7        self.random = random
8"""
9
10class Solution:
11    def __init__(self):
12        # Dictionary to hold old_node -> new_node mapping
13        self.visited = {}
14
15    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
16        if not head:
17            return None
18        
19        # If we have already processed the current node, simply return the cloned version.
20        if head in self.visited:
21            return self.visited[head]
22        
23        # Create a new node with the value same as the old node.
24        new_node = Node(head.val)
25        
26        # Save this value in the hash map. This is needed to avoid loops.
27        self.visited[head] = new_node
28        
29        # Recursively copy the remaining linked list
30        new_node.next = self.copyRandomList(head.next)
31        new_node.random = self.copyRandomList(head.random)
32        
33        return new_node