Problem Statement
Copy List with Random Pointer
A linked list is a chain of nodes. Each node holds a value and a pointer that says "the next node is over here." In this problem each node has an extra pointer called random, which can point to any node in the list, or to nothing (null). Your job is to build a deep copy of the whole list. A deep copy means brand new nodes, not just new arrows to the old ones, so changing the copy never touches the original. The tricky part is the random pointers. When you make a copy of a node, its random should point to the copy of whatever the original's random pointed to, and that copy might not exist yet. We will look at two ways to keep track of which copy belongs to which original. One uses a hash map, which is like a lookup table that maps each original node to its copy, costing O(n) extra space. The other is a clever trick that weaves the copies right into the original list, costing only O(1) extra space.
Signals to notice
Brute force first
Hash map: original → clone. Two passes: clone nodes, then set pointers. O(n) time and space.
The key insight
Interleaving: insert clones after originals (A→A'→B→B'). Set random: clone.random = original.random.next. Separate lists. O(n) time, O(1) extra space.
Trace it on head = [[7,null],[13,0],[11,4],[10,2],[1,0]] (vals 7,13,11,10,1; random idx: 7→null,13→7,11→1,10→11,1→7)
Pass1 interleave: insert clone after each original → 7→7'→13→13'→11→11'→10→10'→1→1' Pass2 set random @7 (random=null): skip; @13 (random=node7): 13'.random = 7.next = 7' Pass2 @11 (random=node1): 11'.random = 1.next = 1'; @10 (random=node11): 10'.random = 11.next = 11' Pass2 @1 (random=node7): 1'.random = 7.next = 7' → all clone randoms set Pass3 capture copy_head = head.next = 7'; separate @7: 7.next=13, 7'.next=13' Pass3 continue: restore 13→11, 11→10, 10→1, 1→null; clones link 7'→13'→11'→10'→1'→null Return copy_head = 7' : clone list [[7,null],[13,0],[11,4],[10,2],[1,0]] independent of original
What must stay true
Interleaving makes each clone accessible via original.next, eliminating the hash map. Random pointers resolve through the interleaved structure.
Shape of the loop
interleave: for each node, splice clone in after it (A→A'→B→B') setRandom: for each original, clone.random = original.random.next separate: for each original, restore original.next, pull out clone chain return copy_head (head.next captured before separating)
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not properly restoring both lists when separating — both original and clone must be cleanly separated.