DSA problem
Copy List with Random Pointer
A linked list of length n is given where each node contains an additional random pointer, which can point to any node in the list or to null. Construct a deep copy of the list: the copy must consist of exactly n brand-new nodes, where each new node has the same value as its original, and the next and random pointers of the new nodes form the same topology as the original list — but the new nodes must point only to other new nodes, never to the original ones.
The challenge is the random pointer. When you create a copy of a node, the node it should randomly point to may not have been created yet, so you cannot simply follow the original random pointer during a single naive pass.
A common approach uses a hash map from each original node to its clone, but that costs O(n) extra space. The optimal solution achieves O(1) extra space using a clever interweaving trick.
The intuition is to weave the cloned nodes directly into the original list: after each original node, insert its clone so the list becomes original1 -> clone1 -> original2 -> clone2 -> .... Now setting random pointers is trivial because clone.random is exactly original.random.next. A final pass separates the two interleaved lists back into the original and the deep copy, restoring the original list intact.
Examples
head = [[7,null],[13,0],[11,4],[10,2],[1,0]][[7,null],[13,0],[11,4],[10,2],[1,0]]head = [[1,1],[2,1]][[1,1],[2,1]]head = [[3,null],[3,0],[3,null]][[3,null],[3,0],[3,null]]Constraints
- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- Node.random is null or is pointing to some node in the linked list.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.