Copy List with Random Pointer
Medium · Linked Lists · Hash Table · Linked List
Problem
Every node of this singly linked list has, besides next, a second pointer random, which points at any node of the list — possibly the node itself — or is None.
Return a deep copy of the list: brand-new nodes, one per original node, with the same values, in which every next and every random points at the corresponding new node. No pointer in the copy may lead back into the original list, and the original must be left exactly as it was.
The node class is Node(x, next=None, random=None), with the value in node.val. The tests build each list with from_pairs([[val, random_index], ...]), where random_index is the position (from 0) of the node that random points at, or None, and read your copy back with to_pairs() in the same form. They also check that none of your nodes is one of the original’s, and that the original reads back unchanged.
Lists here run to 10,000 nodes (LeetCode stops at 1,000), so searching the list for each random target is too slow, and a recursive copy that goes one call deeper per node runs out of stack.
Examples
Input: head = [[7,None],[13,0],[11,4],[10,2],[1,0]] Output: [[7,None],[13,0],[11,4],[10,2],[1,0]]
The copy reads back exactly like the original, but it is made of five new nodes. The random pointer of the new 13 points at the new 7, not the old one.
Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]
Both random pointers target the second node, including the second node itself. In the copy they must target the second new node.
Constraints
- 0 <= n <= 10^4, where n is the number of nodes (LeetCode: at most 1000)
- -10^4 <= Node.val <= 10^4
- Node.random is None or points at a node of the list
Approaches
- Search for each random target’s position — time O(n²), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
