The problem
Each node of this list has a second arrow, random, which can point to any node in the list or to nothing. Build a deep copy: brand-new nodes with the same values, whose next and random arrows point between the new nodes in exactly the same pattern. No arrow in the copy may point into the original.
Here a list is written as [val, random_index] for each node, where random_index is the position of the node its random arrow points to, or null.
Examples
- Input
head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
- Output
[[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
- Input
head = [[1, 1], [2, 1]]
- Output
[[1, 1], [2, 1]]
Constraints
- 0 ≤ number of nodes ≤ 1000
- −10⁴ ≤ Node.val ≤ 10⁴
randomis null or points to a node in the list.
The idea
The hard part is random: when a copy is made, the copy of its random target may not exist yet. A hash map from each original to its copy solves this in two passes, at the cost of O(n) memory.
Without the map: weave each copy right after its original, A → A′ → B → B′. Now the copy of any node X is simply X.next, so a copy’s random is original.random.next. Finally unweave the two lists, restoring the original.
- Time
- O(n) — three passes
- Space
- O(1) besides the copy itself
Solution · every language run against every case
class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': # 1. Put each copy right after its original: A -> A' -> B -> B' -> ... cur = head while cur: cur.next = Node(cur.val, cur.next) cur = cur.next.next # 2. A copy's random is the node right after its original's random. cur = head while cur: cur.next.random = cur.random.next if cur.random else None cur = cur.next.next # 3. Unweave the two lists. dummy = tail = Node(0) cur = head while cur: copy = cur.next cur.next = copy.next tail.next = copy tail, cur = copy, cur.next return dummy.next