125. Copy List with Random Pointer
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.
Examples
Input: [[7,-1],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,-1],[13,0],[11,4],[10,2],[1,0]]
Explanation: The deep copy reproduces every value and random index; -1 marks a null random pointer.
Constraints
- 0 <= n <= 1000; -10^4 <= Node.val <= 10^4; random_index is -1 (null) or a valid index in the list
Run checks all cases above. Submit evaluates all test cases.