Loading problem…
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list: the copy has exactly n brand-new nodes, where each new node's value equals its original node's value, and the next and random pointers of the new nodes mirror the original list's structure — none of the copy's pointers may reference the original list. The list is given and returned as an array where element i is [val, random_index]; random_index is the index of the node the random pointer targets, or -1 for null.
Example 1
Input: nodes = [[7,-1],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,-1],[13,0],[11,4],[10,2],[1,0]]
Explanation: The copy has five new nodes with the same values. Each random pointer targets the same position as in the original: 13 points to index 0 (7), 11 points to index 4 (1), 10 points to index 2 (11), 1 points to index 0 (7), and 7's random pointer is null (-1).
Example 2
Input: nodes = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Explanation: Both nodes' random pointers target index 1 (the node with value 2). The copy points to its own node at index 1, not the original.
Example 3
Input: nodes = [[3,-1],[3,0],[3,-1]]
Output: [[3,-1],[3,0],[3,-1]]
Explanation: All three nodes hold 3, so values alone cannot tell them apart. The copy keeps the exact positions: only the middle node's random pointer is set, pointing to index 0.
The hard part of copying is the random pointer: when you create a clone, the node its random should point to may not exist yet. The trick is to weave each clone right after its original (A → A' → B → B' → …). Now a clone is always reachable as original.next, so 'the clone of X' is simply 'X.next' — which lets us set every random pointer in one pass without a hash map.
Run checks all cases above. Submit evaluates all test cases.