Clone with a map or interleaving

39 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A linked list where each box has two arrows: next, which goes to the following box as usual, and random, which can point to any box in the list or to nothing. Three boxes: 7, 13, 11. next arrows: 7 → 13 → 11. random arrows: 7 → nothing, 13 → 7, 11 → 11 (itself). Make an exact copy: new boxes, same values, same shape of arrows, sharing no box with the original.

By hand, copying the values and the next arrows is easy: walk the list and build 7′ → 13′ → 11′. The random arrows are the problem. The original 13 points at 7; the copy 13′ must point at 7′, not at the original 7. When you reach 13′, how do you find 7′? You could search the new list for the box whose original was 7, but that search walks the list every time: n boxes, each with a walk of up to n, so n² work.

What you need is a lookup: given an original box, find its copy instantly. That is what a map (a dictionary) is for.

Build the structure, one piece at a time

Piece 1: a map from original to copy. A map stores pairs (key, value) and answers "what is the value for this key" in constant time. The keys are original boxes, the values are their copies.

Piece 2: pass one, create copies. Walk the original list. For each box, create a copy with the same value and no arrows yet, and record map[original] = copy.

Piece 3: pass two, wire the arrows. Walk the original list again. For each box, set copy.next = map[original.next] and copy.random = map[original.random], where map[nothing] is nothing.

The result is 7′ → 13′ → 11′ with randoms nothing, 7′, 11′: the same picture, drawn entirely in new boxes.

A variant without the map. Interleave: after each original box insert its copy (7 → 7′ → 13 → 13′ → 11 → 11′). Now the copy of any box x is x.next, which plays the role of the map. Set each copy's random to original.random.next, then unweave the two lists. Same idea, O(1) extra memory.

Why it is correct

The invariant after pass one: every original box has exactly one copy, with the same value, and the map finds it.

Pass two then sets each arrow of each copy to the copy of whatever the original arrow pointed to. So for every arrow in the original there is a matching arrow between the corresponding copies, and no other arrows. That is the definition of an identical structure. Nothing in the copy points into the original because every target is looked up in the map, which only contains copies.

for every box x: copy(x).next = copy(x.next) and copy(x).random = copy(x.random)

The two passes must be separate: during pass one, a random arrow may point forward to a box whose copy does not exist yet, so arrows can only be wired once every copy exists. The same two-pass shape clones a graph, except that a graph is walked by DFS or BFS and the map doubles as the visited set.

Why it is fast

Two walks over n boxes, with constant work per box because each map lookup is constant time.

time = O(n), memory = O(n) for the map (O(1) extra with interleaving)

Versus n² for searching the new list on every random arrow.

How to recognise it in an interview

The cues are "deep copy", "clone", "random pointer", "copy a graph", or any structure with cross-references that must be duplicated without sharing. Say: "First pass creates every copy and maps original to copy; second pass wires each copy's pointers through the map."

Copy List with Random Pointer is the example above. Clone Graph is the same map, filled while traversing: when you meet a neighbour not yet in the map, create its copy and recurse; the map also prevents visiting a node twice.

02The idea in one line

Map old→new (or weave copies in between) so random pointers can be rewired.

Reach for it when: Copy list with random pointer, clone graph, deep copies.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Copy List with Random Pointer on 3 nodes. These are its captions in order, so you can follow without the video or check a step you missed.

1. Pass 1: create a copy of each node and record old → new in a map
2. Copy node 7; map[7] = 7'
3. Copy node 13; map[13] = 13'
4. Copy node 11; map[11] = 11'
5. Pass 2: for each node, set copy.next = map[old.next] and copy.random = map[old.random]
6. 7': next = map[13], random = map[null] = null
7. 13': next = map[11], random = map[7] = 7'
8. 11': next = map[null], random = map[11] = 11'
9. The copy is complete and shares no nodes with the original
10. Two passes, one map: O(n) time and space

04Asked at Google

2 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Linked List: Fast and slow pointers, In-place reversal, Dummy head and splice, Digit-by-digit with carry.