~25 minutes · linked-list cloning · Python · Day 27
Tonight you solve Copy List with Random Pointer. Interviewers like it because ordinary list copying is easy to describe, but the random pointer can jump to any node in the list. The trap is subtle: if a copied node points back into the original list, you did not make an independent copy.
A hashmap from old node to new node lets you wire up arbitrary pointers in a second pass after all clones exist.
That is the whole move. First make every clone node and store the relationship: original node → copied node. Only after that do you connect next and random. The second pass is safe because every pointer target already has a clone waiting in the map.
The map keeps clone pointers independent: an old random target becomes a lookup for the matching cloned target.
Python's dict stores key/value pairs. Here the key is an old node object; the value is its new clone. Dictionary lookup and insertion are average O(1) hash-table operations (Python wiki: time complexity), which is why the map version can stay linear.
Do not key the map by node.val. Values can repeat; node objects are the things being copied.
The brute-force idea is to copy the next chain first. Then, for each original node, find its random target by scanning from the old head, and walk the same number of steps in the copied list to find the matching clone.
old = head
new = copy_head
while old:
scan_old, scan_new = head, copy_head
while scan_old is not old.random: # rescan to find target
scan_old = scan_old.next
scan_new = scan_new.next
new.random = scan_new
old, new = old.next, new.next
This works as an idea, but it is O(n²): each node may trigger another full scan. The better approach keeps the same clone output but spends O(n) extra space so every target clone is one dictionary lookup away.
Use two passes. Pass one creates clone nodes only. Pass two connects arrows. The small trick {None: None} means a missing next or random pointer maps cleanly to None.
Pass one guarantees every target clone exists; pass two turns each old pointer into a map lookup.
def copyRandomList(head):
old_to_new = {None: None} # handles empty next/random
cur = head
while cur: # pass 1: create clones
old_to_new[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur: # pass 2: wire pointers
old_to_new[cur].next = old_to_new[cur.next]
old_to_new[cur].random = old_to_new[cur.random]
cur = cur.next
return old_to_new[head]
The important order is not a syntax detail. A random pointer can point forward, backward, to itself, or to nothing. Creating every clone first removes all of those cases from the wiring step.
Clone Graph: each node has a list of neighbors instead of one next pointer and one random pointer. Before opening the reveal, predict the map. What should the key be, what should the value be, and when is it safe to append cloned neighbors?
The map is still original object → cloned object. For a graph, the second pass may happen inside DFS or BFS, but the invariant does not change: get or create the clone for each old node, then wire each cloned neighbor through the same map. The pointer field changed shape; the old-to-new relationship stayed the same.
| Approach | Time | Space |
|---|---|---|
| Brute force (rescan for random target) | O(n²) | O(1) extra |
| Hashmap clone (two passes) | O(n) | O(n) map |
The output copy itself is O(n) either way. The trade is about extra working memory: a map buys you direct access to every clone, so no pointer target needs a search.
1. What does the clone map store?
2. Why create all clones before wiring random pointers?
3. Spot the bug in this one-pass attempt:
old_to_new = {}
cur = head
while cur:
old_to_new[cur] = Node(cur.val)
old_to_new[cur].random = old_to_new[cur.random]
cur = cur.nextcur.random points forward, that target is not in the map yet. If it is None, this map also has no clean None entry.4. Which task has the same old-to-new map shape?
Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:
For the encode step, write one sentence explaining why the random pointers must be wired after all clones exist.
Watch NeetCode — Copy List with Random Pointer after your attempt, as the compare step. Listen for the moment where the old-to-new map turns arbitrary pointers into ordinary lookups.