Each node of a linked list has a next pointer and an extra random pointer that can point to any node in the list or be null. Build a deep copy: a brand new list of new nodes with the same values, where every copied next and random points to copied nodes, never to the original ones. Return the head of the copy and leave the original list unchanged. Tests describe a list as [val, randomIndex] pairs, where randomIndex is the position the random pointer targets or null.
- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- `Node.random` is null or points to a node in the list
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The straightforward approach uses a hash map from each original node to its copy: one pass creates all copies, a second pass wires next and random through the map. That is O(n) time and O(n) extra space, and is a perfectly good first answer. The space can be removed by storing the mapping inside the list itself: weave each copy directly after its original. Then the copy of any node x is x.next, so the copy's random is x.random.next. A final pass unweaves the two lists, restoring the original.
Algorithm
- Weave: for every node
x, createcopy(x)and insert it betweenxandx.next. - Set randoms: for every original
xwith a random, setx.next.random = x.random.next. - Unweave: walk the list, restoring
x.nextto the next original and linking each copy to the next copy. - Return the first copy (the old
head.next).
O(n)Space: O(1) extra (not counting the copied list)class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': if not head: return None # 1. Weave: A -> A' -> B -> B' -> ... cur = head while cur: copy = Node(cur.val) copy.next = cur.next cur.next = copy cur = copy.next # 2. The copy of x.random is x.random.next. cur = head while cur: if cur.random: cur.next.random = cur.random.next cur = cur.next.next # 3. Unweave and restore the original list. new_head = head.next cur = head while cur: copy = cur.next cur.next = copy.next copy.next = copy.next.next if copy.next else None cur = cur.next return new_head