Copy List with Random Pointer Solution

Problem

Each node in this linked list carries two pointers: next (the usual chain) and random (which can point to any node in the list, or null). Return a completely independent deep copy — brand-new nodes, identical structure.

→

→∅

[7,13,11,10,1]

Input: head of a linked list where each node also has a random pointer (may be null)
Output: head of a deep copy with the same next and random connections
Explanation: the copied list is structurally identical but shares no memory with the original

If node 1 has val = 7 and a random pointing to the node with val = 1, the copied node must also point to the copy of the node with val = 1 — not the original.

Intuition

The wrinkle is that random pointers can point forward in the list, so you can't copy everything in one pass — when you reach node A's random target, that target's copy might not exist yet. The hash map solution breaks this dependency by creating all copies first, then wiring them up in a second pass. The space-optimal trick sidesteps the map entirely by temporarily embedding each copy directly after its original, so that copy.random = original.random.next is always valid — the copy of any node is always one .next step away from the original.

Approach 1 — Hash Map

Build a mapping from every original node to its fresh copy, then assign all pointers in a second pass using the map.

Traverse the list; create a new node for each original and store original → copy in a hash map.
Traverse again; for each node, set copy.next = map[original.next] and copy.random = map[original.random], guarding against null pointers.
Return map[head].

1def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
2    if not head:
3        return None
4
5    node_map = {}  # maps each original node to its deep copy
6
7    current = head
8    while current:
9        node_map[current] = Node(current.val)
10        current = current.next
11
12    current = head
13    while current:
14        if current.next:
15            node_map[current].next = node_map[current.next]
16        if current.random:          # random can be None — guard before lookup
17            node_map[current].random = node_map[current.random]
18        current = current.next
19
20    return node_map[head]

Time: O(n) — two linear passes over the list.
Space: O(n) — the hash map holds one entry per node.

Approach 2 — List Interleaving

Embed each copy node directly after its original (1→1'→2→2'→…) so the copy of any node is always reachable as node.next, eliminating the need for a map.

Interleave: For each original node, create a copy and splice it between the original and original.next.
Set randoms: For each original, copy.random = original.random.next — the copy of original.random is always one .next away.
Separate: Restore the original list while extracting the copy list by advancing two nodes at a time.

1def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
2    if not head:
3        return None
4
5    # Step 1: splice each copy right after its original
6    current = head
7    while current:
8        copy = Node(current.val)
9        copy.next = current.next        # copy inherits what was original's next
10        current.next = copy             # original now leads into its copy
11        current = copy.next             # advance past the copy we just inserted
12
13    # Step 2: set random pointers — copy of X's random is always X.random.next
14    current = head
15    while current:
16        if current.random:
17            current.next.random = current.random.next
18        current = current.next.next     # jump over copy node to reach next original
19
20    # Step 3: separate the two interleaved lists
21    new_head = head.next
22    current = head
23    while current:
24        copy = current.next
25        current.next = copy.next                            # restore original's next link
26        copy.next = copy.next.next if copy.next else None  # connect copy to next copy
27        current = current.next
28    
29    return new_head

Time: O(n) — three linear passes over the list.
Space: O(1) — no auxiliary data structure; copies live temporarily inside the original list.

Complexity Summary

Approach	Time	Space	When to use
Hash Map	O(n)	O(n)	Default — readable, handles all edge cases naturally
List Interleaving	O(n)	O(1)	When extra memory is constrained and you need constant space

Common Mistakes

Forgetting the null guard on random: In Approach 1, accessing node_map[current.random] when current.random is None raises a KeyError in Python or NullPointerException in Java. Always check if current.random before the lookup.
Mixing up steps 2 and 3 in Approach 2: Step 2 relies on the interleaved structure being intact — if you start separating the list before setting all random pointers, current.random.next no longer points to the copy.
Wrong advance in the step-3 loop: After relinking, advance with current = current.next (not current.next.next) because you've already restored current.next to the next original node.
Not restoring the original list: Some callers reuse the original list after your function returns. Skipping the restoration step in Approach 2 permanently corrupts the original's next pointers.
Assuming one pass is enough: A random pointer can point forward, to a node whose copy doesn't exist yet — making a single-pass approach impossible without the interleaving trick.

Copy List with Random Pointer — Solution