The problem
Each node in a linked list has a next pointer and a random pointer that can point to any node or to nothing. Make a deep copy: brand-new nodes whose next and random links mirror the original.
Input: values [7, 13, 11, 10, 1], random → [none, 0, 4, 2, 0] Output: an identical new list (no node shared with the original)
Picture it
Picture a train where each coach also has a buddy link to some other coach. We want to photocopy the whole train. First pass: build a copy of every coach and note in a lookup table “original → copy”. Second pass: for each original coach, wire its copy’s next and buddy to the copies of its next and buddy, found via the table.
How to recognise it
- You must build a deep copy: brand-new nodes, none shared with the original, wired exactly the same way.
- Some links can point anywhere, including backwards or to nodes not created yet, so you cannot wire everything in one forward walk.
- Values may repeat, so a node cannot be identified by its value. You need to identify nodes by identity (which object they are).
- When the question is "for this original node, which copy belongs to it?", a dictionary from old node to new node answers it in O(1). The same idea clones graphs.
Start with brute force
Copy the next chain first. Then, for each random pointer, find its target's position by walking the original list from the head, and walk the copy the same number of steps.
def copy_random_brute(head):
dummy = tail = Node(0)
node = head
while node: # copy values and next links
tail.next = Node(node.val)
tail, node = tail.next, node.next
node, copy = head, dummy.next
while node:
if node.random:
target, i = head, 0 # position of node.random
while target is not node.random:
target, i = target.next, i + 1
other = dummy.next # same position in the copy
for _ in range(i):
other = other.next
copy.random = other
node, copy = node.next, copy.next
return dummy.next
Each random pointer can cost two walks of up to n steps, so time is O(n²) and extra space O(1) beyond the copy. LeetCode allows 1,000 nodes, about 10^6 steps, which still passes, but a list of 10^5 nodes would need about 10^10.
From brute force to the idea
- Find the waste. Both inner walks answer one question: "which copy belongs to this original node?" The brute force recomputes it from the head every time.
- Remember the answer. Store it once in a dictionary
clonethat maps each original node to its copy. Python dictionaries can use node objects as keys; they are compared by identity, so repeated values are no problem. - First pass: make the nodes. Walk the list and create
clone[node] = Node(node.val), with no links yet. Now every copy exists, even ones a random pointer will need later. - Second pass: wire the links. For each original node,
clone[node].next = clone[node.next]andclone[node].random = clone[node.random]. - Handle
Nonewith one entry. The dictionary starts as{None: None}, so a missingnextorrandommaps toNonewithout anif. It also makesclone[head]returnNonefor an empty list.
This is the key idea: a dictionary from original node to copy, filled in one pass and used to wire every pointer in a second.
The key idea
A dictionary from old node to new node lets you wire every pointer in a second pass. O(n).
Python solution
def copy_random(head):
clone = {None: None}
node = head
while node:
clone[node] = Node(node.val)
node = node.next
node = head
while node:
clone[node].next = clone[node.next]
clone[node].random = clone[node.random]
node = node.next
return clone[head]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): up to two walks of n steps per random pointer | O(1) beyond the n new nodes |
| Dictionary, two passes (shown code) | O(n): each pass visits every node once, lookups are O(1) on average | O(n): the dictionary holds one entry per node (plus the n new nodes) |
Edge cases
- Empty list: both loops are skipped and
clone[None]returnsNone. - Random pointing to itself:
clone[node].random = clone[node], so the copy points to itself, not to the original. - Random is
None: handled by the{None: None}entry, no check needed. - Repeated values (
[1, 1], each random pointing to the other): works, because the keys are the node objects, not their values. - Random pointing forwards: fine, since every copy was created in the first pass before any wiring.
- The original is untouched: the shown code only reads the input, so the original list keeps all its links.
Common mistakes
- Writing
clone[node].random = node.random. The copy then points into the original list, which is not a deep copy. - Keying the dictionary by
node.val. Two nodes with the same value overwrite each other's copy. - Wiring
randomduring the first pass, before the target's copy exists, which raisesKeyError. - Forgetting the
Noneentry, so the last node'sclone[node.next]raisesKeyError.
Make the same deep copy without a dictionary, using only O(1) extra space besides the new nodes. The original list must be unchanged afterwards. Describe your approach, then write it if you like.
Compare with our answer
Use the list itself as the lookup table. Insert each copy right after its original (A → A′ → B → B′). Then the copy of any node X is simply X.next, so the copy's random is node.random.next. Finally, unweave the two lists, restoring the original links.
def copy_random_weave(head):
node = head
while node: # 1. A -> A' -> B -> B' ...
node.next = Node(node.val, node.next)
node = node.next.next
node = head
while node: # 2. copy of random is random.next
if node.random:
node.next.random = node.random.next
node = node.next.next
dummy = tail = Node(0)
node = head
while node: # 3. unweave, restoring the original
copy = node.next
node.next = copy.next
tail.next = copy
tail = copy
node = node.next
return dummy.next
Time O(n), extra space O(1) besides the copy.
A strong answer mentions: interleaving so that X.next is X's copy, setting all randoms before unweaving, and restoring the original next links.
1. You must deep-copy a graph where each node has a list of neighbours, and cycles are possible. Which approach fits best?
The dictionary is the same idea as here: it gives each original exactly one copy and stops cycles from being copied forever. Copying on every visit loops on a cycle, values can repeat, and graph nodes have no list positions.
2. Why does the shown code start the dictionary as {None: None}?
Every lookup clone[node.next] or clone[node.random] may get None; the extra entry returns None for those. There is no dummy node in the shown code, and the loops stop on while node.
3. A learner writes clone[node].random = node.random in the second loop. What is wrong with the result?
node.random is an original node, so the copy and the original now share nodes through random. The next links still come from clone, and no lookup is made for random, so no KeyError is raised.
Score 60% or more and the lesson is marked complete.