Copy List with Random Pointer
Deep-copy a linked list whose nodes also point to a random node: copy every node first, then wire next and random through a map.
Problem Understanding
Copy List with Random Pointer: each node has a next pointer and a random pointer that can point to any node in the list, or to None. Return a deep copy: brand-new nodes with the same values, whose next and random pointers mirror the original's, and which point only to other new nodes.
LeetCode writes the list as [[val, random_index], ...], for example [[7,null],[13,0],[11,4],[10,2],[1,0]].
The Intuition: Make the Nodes Before the Pointers
Copying next alone is easy: walk the list and build as you go. The random pointer is the problem, because it can point ahead to a node you have not copied yet.
So split the work into two passes, joined by a map from each original node to its copy:
- Pass 1: for every node, create
Node(node.val)and storecopies[node] = copy. - Pass 2: for every node,
copies[node].next = copies[node.next]andcopies[node].random = copies[node.random], withNonemapping toNone.
By pass 2, every node that any pointer can reach already has a copy. Return copies[head]. This builds on the basics in the linked list guide.
Interactive Walkthrough
COLUMNS ARE POSITIONS · i′ IS THE COPY OF NODE i · — IS NONE
START
0
1
2
3
4
val
random
copy
copy.next
copy.rand
node
—
copies
0
wired
0
5 nodes. A random pointer may point ahead, so copy every node first, then wire them
Next
Pass 1: copy node 0 (value 7) and remember original 0 → copy 0′
head
Legend & Complexity
The original node being visited
Copies made and pointers set
Not made or not set yet
Time
O(n)
Space
O(n) map; O(1) interleaved
Each column is one node, by position. The top rows are the original list; the rows below fill in the copy. Watch pass 1 create every copy, then pass 2 set each copy's next and random to other copies.
Dry Run Table
Input: [[7,null],[13,0],[11,4],[10,2],[1,0]]
| Node | val | random | Copy | copy.next | copy.random |
|---|---|---|---|---|---|
| 0 | 7 | None | 0′ | 1′ | None |
| 1 | 13 | 0 | 1′ | 2′ | 0′ |
| 2 | 11 | 4 | 2′ | 3′ | 4′ |
| 3 | 10 | 2 | 3′ | 4′ | 2′ |
| 4 | 1 | 0 | 4′ | None | 0′ |
Node 2's random points ahead to node 4, which is why the copies are all made first.
The Solution Template
Two passes with a map. C has no built-in hash map, so its snippet uses the interleaving method: copies are woven into the list, randoms are read through the weave, then the lists are split.
Copy List with Random Pointer Code
1var copyRandomList = function(head) {2 const copies = new Map([[null, null]]);3 for (let node = head; node; node = node.next) {4 copies.set(node, new _Node(node.val, null, null));5 }6 for (let node = head; node; node = node.next) {7 copies.get(node).next = copies.get(node.next);8 copies.get(node).random = copies.get(node.random);9 }10 return copies.get(head);11};
Edge Cases & Common Mistakes
- Empty list: return
None. - Random pointing to itself:
[[1,1],[2,1]]has node 1 pointing at node 1; the map handles it like any other node. - Repeated values: key the map on node objects, never on values.
- Returning original nodes: every
nextandrandomin the copy must point to a copy, or the result is not a deep copy. - Interleaving without unweaving: the O(1) method must restore the original list's
nextpointers before returning.
Summary
Random pointers can point ahead, so copy every node first and map original → copy. Then wire each copy's next and random through the map. O(n) time and O(n) space, or O(1) extra space by interleaving the copies into the list.
More practice: DSA interview questions with answers · patterns cheat sheet