Copy List with Random Pointer
Part of Practice: Gaps, Clones & Carries
Each node of a linked list has the usual next pointer plus a random pointer that can aim at any node in the list, or at nothing. Build and return a deep copy of the list: brand-new nodes with the same values, whose next and random pointers connect only to other new nodes, mirroring the original wiring exactly.
No pointer in the copy may touch an original node. The list has up to 1000 nodes.
Examples
- Input:
- head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] (each pair is [value, index that random points to])
- Output:
- [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
The copy has the same shape: for instance the new node 13's random points at the new node 7 (index 0), never at the original node 7.
- Input:
- head = [[1, 1], [2, 1]]
- Output:
- [[1, 1], [2, 1]]
Both random pointers aim at the node at index 1; in the copy they aim at the copied node at index 1.
- Input:
- head = []
- Output:
- []
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.