Copy List with Random Pointer
mediumTime: O(n)Space: O(1)
Signals to notice
deep copy list with random pointersmap original to cloneO(1) space via interleaving
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.
What must stay true
Interleaving makes each clone accessible via original.next, eliminating the hash map. Random pointers resolve through the interleaved structure.
Easy way to go wrong
Not properly restoring both lists when separating — both original and clone must be cleanly separated.