Deep-Copy a List With Random Pointers
A cache node list has both a next pointer and an arbitrary 'random' pointer to any node (or null). Produce a deep copy where the copied nodes mirror the original structure but reference only copied nodes.
Problem
A linked list of length n is given where each node has a next pointer and a random pointer that can point to any node in the list or be null. Construct a deep copy: n brand-new nodes whose value, next, and random pointers replicate the original, referencing only the new nodes. Return the head of the copy.
Input
The head of a linked list; each node has an integer val, a next pointer, and a random pointer (index or null in serialized form).
Output
The head of the deep-copied list.
Constraints
- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- random points to a node in the list or is null.
Examples
Example 1
Input
[[7,null],[13,0],[11,4],[10,2],[1,0]]
Output
[[7,null],[13,0],[11,4],[10,2],[1,0]]
A structurally identical copy with independent nodes.
Example 2
Input
[]
Output
[]
Empty list copies to empty.