Copy List with Random Pointer

You are given a linked list where each node has Next and Random pointers. Return a deep copy of the list.

Why this is worth learning

Deep copying requires preserving relationships, not just values. A map from original identity to clone identity lets forward and backward random links be connected after all clones exist.

Before coding: one-minute experiment

If two original nodes point Random to the same third node, should the clone contain one or two copies of that target?

Function signature

func CopyRandomList(head *Node) *Node

Inputs / outputs

• head: head of the original list (may be nil).
• Return: head of the cloned list.

Example

1 -> 2 -> 3
random: 1->3, 2->1, 3->nil
Output: a new list with the same next/random structure

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

Copying only the Next chain is easy, but each Random target may point forward, backward, or to a node already copied for another edge. Allocating a new target on every encounter would duplicate shared objects. First allocate one clone per original pointer and remember that correspondence; then each edge can be translated through it regardless of traversal order. A map keyed by Val is insufficient because two originals may have the same payload. An interleaving alternative can reduce auxiliary storage, but must temporarily alter and then exactly restore the original links; the map approach makes ownership simpler.

Invariant: for every original node in the map, its clone is unique and reused for all references.

Algorithm (step-by-step)

1. If head is nil, return nil.
2. First pass: traverse the list and create clone[node] = new Node(node.Val).
3. Second pass: for each original node:
   • clone[node].Next = clone[node.Next].
   • clone[node].Random = clone[node.Random].
4. Return clone[head].

Correctness sketch

In the first pass, allocate exactly one clone for every node in the finite next chain and record the original-to-clone map. The map is injective because each original receives a fresh allocation. In the second pass, assign each clone's Next and Random to the mapped copies of the original targets; nil maps to nil. Every original edge is thereby reproduced between clone identities, including self-random edges, backward links, and several nodes sharing one random target. No clone points into the original list, and no original edge or value is modified. Thus the result is a graph-isomorphic deep copy.

Trace (hand walkthrough)

Example input:
1 -> 2 -> 3
random: 1->3, 2->1, 3->nil
Output: a new list with the same next/random structure

Walk:
- clone nodes: 1->1', 2->2', 3->3' (map originals to clones)
- wire next: 1'->2'->3'
- wire random: 1'.random=3', 2'.random=1', 3'.random=nil

Pitfalls to avoid

• Using node values as keys (values can repeat in general; use pointers).
• Forgetting to handle nil random pointers.
• Creating new nodes on every reference instead of reusing the same clone.

Debugging lens

Use duplicate node values, self-random links, nil random links, and shared random targets. Build the original-to-clone correspondence by position and assert pointer disjointness and unchanged original edges.

Complexity

• Time: O(n).
• Extra space: O(n) for the map.

Implementation notes (Go)

• Use map[*Node]*Node.
• An alternative O(1) space method is the interleaving trick, but the map solution is simpler and clear.

Contract precision

The Next chain is finite. Every Random pointer is nil or points to a node in that chain. All nodes are deeply copied; the original structure remains unchanged.

Reconstruction checkpoint

A and B both hold 5; A.Next=B, A.Random=A, and B.Random=A. Describe all copied edges and explain why a map keyed by value cannot work.

Return to Linked List · Module quiz