Copy List with Random Pointer

Hash map dictionary: clone every node, then rewire next/random by lookup

time O(n)space O(n) for the map

Cloning next pointers alone is a plain list copy. The random pointer is what makes this hard: it can point at a node anywhere in the list, including one that has not been cloned yet if the scan is only left to right. The array view here shows the original node values; the cur pointer walks the list while the random pointer (when a node has one) marks which index that node's random target lives at. The fix is two passes: first clone every node and store original-to-clone in a hash map, with no wiring yet. Once every node has a clone waiting in the map, a second pass can safely set clone.next and clone.random by looking up map[original.next] and map[original.random] — order no longer matters because every possible target already has a clone.

Details

Animated on: A linked list where each node also has a random pointer that can point to any node or null. Values [7, 13, 11, 10], random targets by index [none, 0, 3, 1]. Produce a completely independent deep copy with the same structure.

Problem:Copy List with Random PointerMedium

Pattern:Linked List Manipulation

Hash map dictionary: clone every node, then rewire next/random by lookup

step 1 / 10

[0]

[1]

[2]

[3]

4 nodes with values [7, 13, 11, 10]. Random targets by index: [none, 0, 3, 1] — node 1's random points at node 0, node 2's at node 3. A random pointer can jump anywhere, even forward to a node not cloned yet, so a single left-to-right pass cannot wire it up immediately.

cur=0· arr[0] = 7

Pseudocode

1FUNCTION copyRandomList(head)
2  IF head = NULL
3    RETURN NULL
4  map <- EMPTY MAP
5  cur <- head
6  WHILE cur != NULL
7    map[cur] <- NEW NODE(cur.val)
8    cur <- cur.next
9  cur <- head
10  WHILE cur != NULL
11    map[cur].next <- map[cur.next]
12    map[cur].random <- map[cur.random]
13    cur <- cur.next
14  RETURN map[head]

← / → step · space play · Home restart

Every step in words

Show all 10 steps

4 nodes with values [7, 13, 11, 10]. Random targets by index: [none, 0, 3, 1] — node 1's random points at node 0, node 2's at node 3. A random pointer can jump anywhere, even forward to a node not cloned yet, so a single left-to-right pass cannot wire it up immediately.
Clone node 0 (val=7) and remember map[original node 0] = new clone. This pass only allocates clones and records the mapping — next/random on the clone are still unset, so it does not matter yet whether a target has been cloned.
Clone node 1 (val=13) and remember map[original node 1] = new clone. This pass only allocates clones and records the mapping — next/random on the clone are still unset, so it does not matter yet whether a target has been cloned.
Clone node 2 (val=11) and remember map[original node 2] = new clone. This pass only allocates clones and records the mapping — next/random on the clone are still unset, so it does not matter yet whether a target has been cloned.
Clone node 3 (val=10) and remember map[original node 3] = new clone. This pass only allocates clones and records the mapping — next/random on the clone are still unset, so it does not matter yet whether a target has been cloned.
clone[0].next <- map[node 1]. Node 0's random pointer is null in the original, so clone[0].random stays null too — nothing to look up.
Every clone already exists in the map, so both pointers can be wired in one lookup: clone[1].next <- map[node 2], and clone[1].random <- map[node 0] (val=7). The map is what makes a forward-pointing random pointer safe here — it was already cloned in the first pass regardless of scan order.
Every clone already exists in the map, so both pointers can be wired in one lookup: clone[2].next <- map[node 3], and clone[2].random <- map[node 3] (val=10). The map is what makes a forward-pointing random pointer safe here — it was already cloned in the first pass regardless of scan order.
Every clone already exists in the map, so both pointers can be wired in one lookup: clone[3].next <- map[node null], and clone[3].random <- map[node 1] (val=13). The map is what makes a forward-pointing random pointer safe here — it was already cloned in the first pass regardless of scan order.
All 4 nodes cloned and rewired via the map in two O(n) passes — O(n) time, O(n) extra space for the map. Returning map[original head] hands back a fully independent list: every next and random pointer targets a clone, never an original node.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Copy List with Random Pointer in the editor All Linked List problems Back to roadmap