Copy List with Random Pointer
Deep-copy a list where each node also has a random pointer to any node (or null).
02
Intuition
The hard part is wiring random in the copy — the target may not exist yet when you meet the pointer. Interleave copies with originals (A→A'→B→B'…): then every original's random copy is exactly random.next, no map needed.
03
Approach
1
Pass 1 — interleave
After each original node insert its clone: A→A'→B→B'. Clones are reachable from their originals in O(1).
2
Pass 2 — wire randoms
For each original cur, its clone's random is cur.random.next (the clone of cur.random). Nulls pass through.
3
Pass 3 — unweave
Split the interleaved list back into original and copy, restoring the original intact.
04
Solution & live demo
python
▶1class Solution:
▶2 def copyRandomList(self, head):
▶3 if not head: return None
▶4 cur = head # 1) interleave clones
▶5 while cur:
▶6 nxt = cur.next
▶7 cur.next = Node(cur.val, nxt)
▶8 cur = nxt
▶9 cur = head # 2) wire randoms
▶10 while cur:
▶11 if cur.random:
▶12 cur.next.random = cur.random.next
▶13 cur = cur.next.next
▶14 cur, copy_head = head, head.next
▶15 while cur: # 3) unweave
▶16 clone = cur.next
▶17 cur.next = clone.next
▶18 clone.next = clone.next.next if clone.next else None
▶19 cur = cur.next
▶20 return copy_head
05
Edge cases
random is null
Guard: only assign when cur.random exists.
random points to itself
cur.random.next is the node's own clone — works unchanged.
06
Complexity
Time
O(n)
Space
O(1)
Three passes; no hash map thanks to interleaving.