138 · Copy List with Random Pointer

Clone a linked list — random pointers and all.

Think of a master blueprint where each page has both forward instructions and handwritten cross-references to arbitrary other pages. A simple photocopy duplicates the forward chain — but its cross-references still point into the original manual. The interleaving trick solves this: slip each copied page right after its original, so every cross-reference is exactly one page-turn from its duplicate. Assign cross-references through that single-hop path, then separate the copies into their own manual. Three passes through the list. O(n) time. O(1) extra space.

Interactive

Watch interleave, assign, and split in action

Concept

Three passes, no hash map

The interleaving technique deep-copies a linked list with random pointers using constant extra space. Each phase solves a specific part of the problem.

Interleave

Clone each node and splice it right after the original: A → A′ → B → B′ → C → C′. Every clone now sits exactly one .next hop from its original. No hash map is needed to locate a clone — it's always at original.Next.

original.Next = clone; clone.Next = nextOriginal

One-hop random

Because each clone sits right after its original, original.Random.Next is always the clone of the random target. This single-hop detour is the key insight that makes the O(1) space approach possible — every random connection can be resolved through one extra pointer dereference.

clone.Random = original.Random.Next

Split

Unweave the interleaved chain: restore each original's .next to skip its clone, and link each clone's .next to the following clone. Both the original and copied lists emerge fully intact with correct structure.

original.Next = clone.Next; clone.Next = nextClone

Algorithm

Interleave, assign random, split — three clean passes

Each pass walks the list once. The interleave creates the woven structure, the assign leverages it, and the split undoes it — leaving two independent lists with identical topology.

1

Interleave clones

Walk the original list. For each node, create a clone with the same value and splice it in immediately after: original → clone → nextOriginal. Advance to clone.Next (the next original). After this pass, the list is twice as long with each original followed by its clone.
2

Assign random pointers

Walk the woven list two nodes at a time. For each original that has a random pointer, set clone.Random = original.Random.Next. The .Next of any original is its clone — so this one hop resolves the target without a lookup table.
3

Split the woven list

Walk the woven list one last time. Restore each original's .next pointer to skip its clone. Link each clone's .next to the following clone. Use a dummy head to collect the clone chain. Return dummyHead.Next.

Edge Cases

When cloning is not straightforward

Two situations test whether the copy correctly refers to its own nodes rather than back into the original list.

Null random pointer

When an original node has no random pointer, the assign phase simply skips it — the clone's random stays null by default. The if (original.Random != null) guard prevents a null-dereference and correctly propagates the absence. Try the "No random pointers" preset.

Self-referencing random

When a node's random pointer points to itself, original.Random.Next is the clone sitting right after that original — which is the node's own clone. The clone correctly ends up pointing to itself, not back to the original. Try the "[1→self]" preset.