Copy List with Random Pointer

You are given the head of a linked list of length n. Each node has a val, a next pointer, and a random pointer that may point to any node or null. Create a deep copy: exactly n new nodes, no pointers into the original list.

Examples

• 0 ≤ n ≤ 100
• -100 ≤ Node.val ≤ 100
• random is null or points to some node in the list.

1. Recursion + Hash Map

Intuition

Use a hash map to memoize every node we've cloned. On each call, if the node is already in the map return its copy; otherwise create the copy, store it, then recurse for next and look up random.

• Base: head is None → return None.
• If head in map return cached copy (handles shared random targets).
• Create copy, store in map, recurse next, then wire random.

Time: O(n)  |  Space: O(n) map + O(n) stack

2. Hash Map — Two Pass Optimal time · O(n) space

Intuition

Pass 1: traverse and create a copy for every node, storing original → copy in a map. Pass 2: traverse again and wire copy.next and copy.random by looking up the map. All copies exist before any pointer is wired.

• Init oldToCopy = { None: None }.
• Pass 1: create and store every copy.
• Pass 2: wire next and random for every copy.
• Return oldToCopy[head].

Time: O(n)  |  Space: O(n)

3. Hash Map — One Pass Optimal time · O(n) space

Intuition

Python's collections.defaultdict auto-creates a new Node(0) when a key is first accessed. In a single pass, set val, next, and random simultaneously — accessing oldToCopy[cur.next] creates the stub for cur.next on the fly if it hasn't been visited yet. Gray nodes in the visualization are those pre-created stubs.

• Init defaultdict; oldToCopy[None] = None.
• For each cur: set val, next, random in one iteration.
• The defaultdict ensures stubs are promoted to full copies when their turn comes.

Time: O(n)  |  Space: O(n)

4. Space Optimized I — Interleave via next O(1) extra space

Intuition

Weave copy nodes into the original list using next pointers: A → A' → B → B' → …. Each copy sits immediately after its original, so A.random.next gives the copy of A's random target — no hash map needed.

• Pass 1 — Interleave: for each node A, create A' and insert it as A.next.
• Pass 2 — Randoms: A'.random = A.random.next (if random ≠ null).
• Pass 3 — Unweave: restore A.next and link A'.next = A'.next.next.

Time: O(n)  |  Space: O(1) extra (O(n) output)

5. Space Optimized II — Interleave via random O(1) extra space

Intuition

Instead of the next pointer, temporarily use random to store copies: set A.random = A' (copy) and A'.next = A's original random target. The purple downward arrows in the visualization show this temp random-as-map link.

• Pass 1: for each A: create A', set A'.next = A.random (save), set A.random = A' (map).
• Pass 2: A'.random = A'.next.random if A'.next else None.
• Pass 3: restore A.random = A'.next; link A'.next = A.next.random if A.next.

Time: O(n)  |  Space: O(1) extra (O(n) output)

Common Pitfalls

Creating Multiple Copies of the Same Node

Without a map, multiple random pointers targeting the same node each trigger a fresh Node(...), producing duplicates. Always check the map first.

# Wrong — creates a new copy every time:
copy.random = Node(original.random.val)

# Correct — reuse from map:
copy.random = oldToCopy[original.random]

Forgetting to Handle Null Random Pointers

The map must include a None → None entry (Python) or a null check; otherwise accessing oldToCopy[null] throws a KeyError / NullPointerException.

Not Restoring the Original List (Space-Optimized)

In the interleaving approach, the unweave pass must correctly restore original.next to point to the next original node. Failing corrupts the original list and may break the copy list's own chain.