Copy List with Random Pointer — HashMap Clone and O(1) Space Interleave

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 copies represent the same list state. None of the pointers in the new list should point to nodes in the original list.

Constraints:

• 0 <= n <= 1000
• -10^4 <= Node.val <= 10^4
• Node.random is null or points to some node in the 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]]
Explanation: Each pair is [node.val, node.random.index].

Example 2:

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

Why This Problem Matters#

Copy List with Random Pointer (LeetCode 138) is one of the most elegant medium problems in the linked list section. Amazon, Microsoft, and Facebook ask it because it tests two things: whether you understand deep copy semantics (not just pointer copying), and whether you can come up with the O(1) space interleave trick as an optimization.

The challenge is the random pointer. If you create copies of nodes in a single forward pass, when you try to set copy.random, the target random node might not have been created yet. This ordering problem requires either two passes (create all nodes first, then set pointers) or an on-demand approach using a hash map.

The O(n) space hash map solution is the standard approach. The O(1) space interleave solution is the "wow" solution that interviewers look for as a follow-up. Both are important to know.

This problem directly tests your understanding of reference semantics vs value semantics — a fundamental concept in any language with objects and pointers. In production code, deep copying is a common operation: copying configurations, cloning game states, creating edit-safe snapshots of data structures.

The Core Insight#

Hash map approach: Create a mapping from original node → copy node. First pass: create all copy nodes and populate the map. Second pass: use the map to set copy.next and copy.random — since all copies exist now, any reference can be resolved instantly.

Interleave approach (O(1) extra space):

1. Interleave original and copy nodes: orig -> copy -> orig.next -> ...
2. Set random pointers: copy.random = orig.random.next (the copy of orig.random is immediately after it)
3. Separate the two lists by restoring the original and extracting the copy list

The interleave approach is brilliant because it encodes the mapping between original and copy nodes directly in the list structure — eliminating the hash map.

Visual Dry Run#

Input: A -> B -> C, where A.random = C, B.random = A, C.random = None

Hash Map Approach:

Pass 1 (create copies):

• map[A] = A', map[B] = B', map[C] = C'

Pass 2 (set pointers):

• A'.next = map[A.next] = map[B] = B'
• A'.random = map[A.random] = map[C] = C'
• B'.next = map[B.next] = map[C] = C'
• B'.random = map[B.random] = map[A] = A'
• C'.next = map[C.next] = map[None] = None
• C'.random = map[C.random] = map[None] = None

Interleave Approach:

Step 1 — Interleave: A -> A' -> B -> B' -> C -> C'

Step 2 — Set random pointers:

• A.random = C, so A'.random = A.random.next = C.next = C'
• B.random = A, so B'.random = B.random.next = A.next = A'
• C.random = None, so C'.random = None

Step 3 — Separate:

• Original: A -> B -> C (restore A.next=B, B.next=C, C.next=None)
• Copy: A' -> B' -> C'

Solution (Optimal)#

Python — Hash Map (O(n) space)#

def copyRandomList(head):
    if not head:
        return None
 
    # Map original nodes to their copies
    old_to_new = {None: None}  # handle null references cleanly
 
    # Pass 1: Create all copy nodes
    curr = head
    while curr:
        old_to_new[curr] = Node(curr.val)
        curr = curr.next
 
    # Pass 2: Set next and random pointers
    curr = head
    while curr:
        old_to_new[curr].next = old_to_new[curr.next]
        old_to_new[curr].random = old_to_new[curr.random]
        curr = curr.next
 
    return old_to_new[head]

Python — Interleave (O(1) extra space)#

def copyRandomList(head):
    if not head:
        return None
 
    # Step 1: Interleave original and copy nodes
    curr = head
    while curr:
        copy = Node(curr.val)
        copy.next = curr.next
        curr.next = copy
        curr = copy.next  # skip over the copy to next original
 
    # Step 2: Set random pointers for all copies
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next  # copy.random = orig.random's copy
        curr = curr.next.next  # skip copy, move to next original
 
    # Step 3: Separate the two lists
    curr = head
    new_head = head.next
    while curr:
        copy = curr.next
        curr.next = copy.next        # restore original list
        copy.next = copy.next.next if copy.next else None  # advance copy list
        curr = curr.next             # move to next original
    
    return new_head

JavaScript — Hash Map#

var copyRandomList = function(head) {
    if (!head) return null;
 
    const map = new Map();
    map.set(null, null);
 
    let curr = head;
    while (curr !== null) {
        map.set(curr, new Node(curr.val));
        curr = curr.next;
    }
 
    curr = head;
    while (curr !== null) {
        map.get(curr).next = map.get(curr.next);
        map.get(curr).random = map.get(curr.random);
        curr = curr.next;
    }
 
    return map.get(head);
};

Complexity:

Common Mistakes#

1. Setting random before all copy nodes exist. In a single pass, when you try to set copy.random, the target's copy might not exist yet. Two passes (create all, then wire) or the hash map solves the ordering problem.

2. Not including None: None in the hash map. When curr.random = None, old_to_new[None] must return None. Without {None: None} in the initial map, accessing old_to_new[curr.random] when curr.random = None raises a KeyError.

3. In the interleave approach: forgetting to handle curr.random = None. curr.next.random = curr.random.next crashes if curr.random = None. Guard with if curr.random: curr.next.random = curr.random.next.

4. In the interleave separation step: losing the original list. When separating, you must carefully restore curr.next to copy.next (the next original) before advancing. If you set copy.next first and lose the reference to the next original, you can't restore the list.

5. Returning the wrong node. Save new_head = head.next before the separation phase. After separation, head.next has been restored to the original list's second node. If you return head.next after separation, you return the wrong node.

Interview Tips#

1. Lead with the hash map: "The straightforward approach is a hash map: create all copies first, then wire next and random using the map. This is O(n) time and O(n) space."

2. Then offer the interleave: "If O(1) space is required, there's an elegant interleave technique: place each copy right after its original. The copy of any node's random is immediately after the original's random."

3. Draw the interleave: A -> A' -> B -> B' -> C -> C'. Show how A'.random = A.random.next works visually.

4. Emphasize the separation complexity: The separation step is the trickiest part of the interleave approach — walk through it carefully.

5. Mention the {None: None} trick: "I initialize the map with None → None so that null random pointers resolve correctly without special-casing."

Follow-up Questions#

Q: What if nodes have unique IDs instead of using object identity as keys? Use node IDs as hash map keys. Same two-pass structure. The hash map maps old_id → new_node.

Q: Can you do it with O(1) space without the interleave trick? Not without modifying the original list temporarily (which the interleave technique does). If you cannot modify the original at all, O(n) space is required.

Q: What if the random pointer can point outside the list? Then you'd need to handle external references. The hash map approach is still valid — you'd just need to clone any externally referenced nodes too. This becomes a general graph clone problem (LC 133, Clone Graph).

Q: How does this relate to Clone Graph (LC 133)? This is essentially Clone Graph for a linear data structure. Clone Graph uses BFS/DFS + hash map for an arbitrary graph. Copy List with Random Pointer is the linked-list-specific version.

Q: What is the space complexity of the interleave approach? O(1) extra space — no hash map. The copy nodes are allocated (which is O(n) total but required for the output) but no auxiliary data structure is used.

Key Takeaways#

• The two-pass hash map (O(n) space) is the standard approach: create all copies, then wire next and random.
• Initialize the map with {None: None} to handle null random pointers cleanly.
• The interleave technique (O(1) extra space): interleave copies, set random via curr.random.next, separate the lists.
• Guard curr.random before accessing curr.random.next in the interleave random-setting step.
• In the interleave separation, save the next pointers before overwriting.
• The interleave approach is a "wow factor" follow-up — always have it ready when the interviewer asks for O(1) space.