visual walkthrough
Copy List with Random Pointer
Deep copy with arbitrary pointers; the interleaving trick gives O(1) space.
The idea
The hard part is random: when you copy a node, the node its random points to may not have been copied yet. So make all the copies first, then wire them up.
A map from original to copy answers "where's the copy of X?". Or put each copy right after its original, and the answer is just X.next.
Complexity
| approach | time | space |
|---|---|---|
| Original → copy map | O(n) | O(n) |
| Interleave copies | O(n) | O(1) extra |