Clone Linked List with Random Pointer
Implement copyRandomList
Each node in this list carries an extra pointer, alongside the usual next one, that can point at any node in the list — including itself, or nowhere at all. Build a completely independent deep copy: new nodes with the same values, wired into the same next-order and pointing their own random links at the corresponding new nodes, never at any of the original ones.
The trouble with a naive copy is that a random pointer might target a node that doesn't exist yet, or loop back to one already being built. A hashmap keyed by each node's original position solves this cleanly: once every new node is known to a lookup table, wiring .next and .random for any of them is just a lookup away, regardless of which direction it points or whether the target was created a moment ago or hasn't been reached yet.
Example 1:
Input: values = [7,3,9], randomIndices = [2,-1,0]
Output: [[7,2],[3,-1],[9,0]]
Example 2:
Input: values = [5], randomIndices = [-1]
Output: [[5,-1]]
Example 3:
Input: values = [], randomIndices = []
Output: []
+ 6 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 200 - ●
-1000 ≤ node value ≤ 1000 - ●
This platform's judge represents each node's random pointer as an index: randomIndices[i] is the position of the node that node i's random pointer targets, or -1 for none
values =
[7, 3, 9]
randomIndices =
[2, -1, 0]