Appearance
4.9.5 — Copy List with Random Pointer
LeetCode 138 · Medium · ★ Blind 75
The problem
You are given the head of a linked list where every node has two pointers. next points to the following node, as usual. random can point to any node in the list, including the node itself or an earlier one, or it can be null. Make a deep copy of the list and return its head.
A deep copy is a completely new set of nodes with the same values and the same pointer shape. No pointer in the copy may point back into the original list.
original: 7 → 13 → 11 → 10 → 1
random: 7→null, 13→7, 11→1, 10→11, 1→7
the copy must have new nodes 7', 13', 11', 10', 1'
with 13'.random = 7', 11'.random = 1', and so onThe list has between 0 and 1,000 nodes.
What the problem is really asking
Copying next alone is easy. Walk forward and build a new node for each old one.
random is the problem. Suppose you are copying node 13, and its random points to node 7. You need 13'.random to point to 7', the copy of 7, not to the original 7. And for some nodes, the target's copy may not exist yet. When you copy node 11, its random points to node 1, which you have not reached.
So the real question is: how do you find "the copy of this old node", even for nodes you have not copied yet?
The brute force, and where it wastes work
Copy the list using only next. Then, for each original node, count how many steps from the head its random target sits. Walk the same number of steps in the copy, and point the copy's random there.
Counting the steps for one node takes up to n steps. Doing it for all n nodes is O(n^2).
The waste in one sentence: it rediscovers each node's position by walking from the head, again and again, when a lookup table could remember "old node → its copy" once.
The idea
Do it in two passes, with a hash map from each old node to its new copy.
- First pass. Walk the original list and create a copy of every node, with the right value but no pointers yet. Record each pair in the map: old node → new node.
- Second pass. Now every copy exists. Walk the original list again. For each old node, look up its copy, and set the copy's
nextandrandomby looking up the copies of the old node'snextandrandom.
Think of cloning a group of friends who are holding hands in a line and each pointing at their best friend. In the first pass, you make a clone of every person and stand them in a corner, writing in a notebook "original Bob → clone Bob". In the second pass, you look at original Bob. He holds hands with original Alice and points at original Charlie. You look in the notebook to find clone Alice and clone Charlie, and tell clone Bob to hold hands with one and point at the other.
The solution
python
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head: # (1)
return None
old_to_new = {} # (2)
curr = head # (3)
while curr:
old_to_new[curr] = Node(curr.val)
curr = curr.next
curr = head # (4)
while curr:
copy = old_to_new[curr] # (5)
copy.next = old_to_new.get(curr.next) # (6)
copy.random = old_to_new.get(curr.random) # (7)
curr = curr.next
return old_to_new[head] # (8)ts
function copyRandomList(head: Node | null): Node | null {
if (!head) return null; // (1)
const oldToNew = new Map<Node, Node>(); // (2)
let curr: Node | null = head; // (3)
while (curr) {
oldToNew.set(curr, new Node(curr.val));
curr = curr.next;
}
curr = head; // (4)
while (curr) {
const copy = oldToNew.get(curr)!; // (5)
copy.next = curr.next ? oldToNew.get(curr.next)! : null; // (6)
copy.random = curr.random ? oldToNew.get(curr.random)! : null; // (7)
curr = curr.next;
}
return oldToNew.get(head)!; // (8)
}Line by line
(1) An empty list copies to an empty list.
(2) The notebook. A map whose keys are the original node objects and whose values are their copies.
Using node objects as keys works because, by default, Python and JavaScript compare objects by identity, meaning "is this the very same object in memory". Two different nodes that happen to hold the same value stay separate keys. That is exactly what we want here, because each original node needs its own copy.
This is the opposite of 4.4.4 Group Anagrams. There, comparing arrays by identity was the bug, because we wanted arrays with equal contents to match. Here we are tracking particular objects, so identity is right.
(3) First pass: create every copy. For each original node, make a new node with the same value and record the pair. No pointers are set yet, because the targets may not exist yet.
(4) Second pass. Walk the original list again. Now every copy exists.
(5) Find this node's copy.
(6) Set the copy's next to the copy of the original's next. We use .get(...) instead of [...]. When curr.next is None, None is not a key in the map, so old_to_new[None] would raise an error. .get(None) returns None instead, which is exactly the value we want to store. One method call replaces an if.
(7) Set the copy's random the same way.
(8) Return the copy of the head.
Trace
Take a three-node list: A → B → C, where A.random = C, B.random = A, and C.random = None.
After the first pass, the map holds A → A', B → B', C → C'. The copies have values but no pointers.
Second pass:
curr | copy | copy.next = copy of curr.next | copy.random = copy of curr.random |
|---|---|---|---|
| A | A' | B' | C' |
| B | B' | C' | A' |
| C | C' | None | None |
The copy is A' → B' → C', with A'.random = C' and B'.random = A'. Not one pointer leads back into the original.
Complexity, derived
Time. Each pass walks the list once, doing constant-time map work per node. Two passes of n steps is 2n, which is O(n).
Space. The map holds one entry per node, so it uses O(n) extra memory. (The copied list itself is the answer, so it is not counted as extra.)
The version with no map
There is a clever solution that stores the "old → copy" link inside the list itself, so no map is needed.
Step 1. Put each copy right behind its original.
A → B → C
becomes
A → A' → B → B' → C → C'Now, for any original node curr, its copy is simply curr.next.
Step 2. Set the random pointers. The copy of curr.random is curr.random.next. So:
python
curr.next.random = curr.random.next if curr.random else NoneThe list's own shape is doing the job the map was doing.
Step 3. Separate the two lists, and restore the original's next pointers.
python
class Solution:
def copyRandomList(self, head):
if not head:
return None
curr = head # 1. weave copies in
while curr:
curr.next = Node(curr.val, curr.next) # new node points to the old next
curr = curr.next.next # jump over the new node
curr = head # 2. set randoms
while curr:
if curr.random:
curr.next.random = curr.random.next # the copy of the target
curr = curr.next.next
old, new_head = head, head.next # 3. unweave
while old:
copy = old.next
old.next = copy.next # original skips its copy
copy.next = copy.next.next if copy.next else None # copy skips the next original
old = old.next
return new_headThis is O(n) time and O(1) extra memory. It takes three passes instead of two, and it changes the input list for a while, which is a real objection in shared code.
Lead with the map version. It is clearly correct and easy to explain. Offer the woven version when asked to save memory, and mention that it temporarily changes the input.
Edge cases
- Empty list. Line (1) returns
None. - A node whose
randompoints to itself. The map lookup returns its own copy. Correct. - Every
randomisNone..get(None)returnsNoneeach time. - Nodes with equal values. Identity keys keep them separate.
Variations you will meet
- Clone Graph. The same problem on a graph instead of a list. The walk becomes a depth-first or breadth-first search, and the map does exactly the same job. See 4.20.2. If you see these two as one problem, you understand both.
- Deep-copying any data with shared references. When a program copies an object that refers to the same inner object twice, it keeps a map of "already copied" objects, so that inner object is copied once and both references point to the same copy. That is this page, in real software.
The general lesson: when a copy must keep references to objects that may not exist yet, create all the objects first while recording old → new, then wire the pointers in a second pass.
What the interviewer will push on
"Why can't you do it in one pass?" A random pointer can point forward to a node whose copy does not exist yet. Saying this before you code shows you understood the problem.
"What are the keys in your map?" The original nodes themselves, compared by identity. Using values as keys would merge different nodes that share a value.
"Can you do it without the map?" The weaving trick. Mention its cost: it changes the input for a while.
"How does this relate to cloning a graph?" Same problem, different walk.
One thing to volunteer: say that real deep-copy routines do exactly this with shared references. It shows you know the problem is real.
Next: 4.9.6 Add Two Numbers. Arithmetic on a list, with a carry that must survive past the end.