Copy List with Random Pointer
mediumTime: O(n)Space: O(1)
Recognize the pattern
deep copy list with random pointersmap original to cloneO(1) space via interleaving
Brute force idea
Hash map: original → clone. Two passes: clone nodes, then set pointers. O(n) time and space.
Better approach
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.
Key invariant
Interleaving makes each clone accessible via original.next, eliminating the hash map. Random pointers resolve through the interleaved structure.
Watch out for
Not properly restoring both lists when separating — both original and clone must be cleanly separated.