Copy List with Random Pointer
Problem
Each node in a linked list has a next pointer and a random pointer that can point to any node in the list or be null. Build a deep copy made entirely of new nodes, where every next and random pointer in the copy points into the copy rather than the original.
Examples
Constraints
- • 0 <= n <= 1000
- • random is null or points to a node in the list
Hints & approach
Hint 1
The difficulty is that a random target may not have been copied yet.
Hint 2
A map from original node to its copy solves that in two passes.
Hint 3
For O(1) extra space, interleave each copy right after its original.
Approachtry the hints first
The hash-map version makes one pass to create a copy of every node and store original -> copy, then a second pass to set copy.next = map[orig.next] and copy.random = map[orig.random]. The constant-space version weaves copies into the list (A -> A' -> B -> B'), so each copy's random is simply orig.random.next. A final pass unweaves the two lists, restoring the original and extracting the copy.
Time O(n) · Space O(1) extra with interleaving