Copy List with Random Pointer
A linked list of length `n` is given where each node contains an additional `random` pointer, which may point to any node in the list or to `null`. Construct a **deep copy** of the list: the copy should consist of exactly `n` brand new nodes, where each new node's value is set to the value of its corresponding original node. The `next` and `random` pointers of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. **None of the pointers in the new list should point to nodes in the original list.** Each node is `{ val: number, next: Node|null, random: Node|null }`. Implement `copyRandomList(head)` returning the head of the copied list (or `null` for an empty list). You must not modify the original list.
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]→[[7,null],[13,0],[11,4],[10,2],[1,0]]— Each entry is [val, random_index]; random_index is the position the random pointer targets, or null. The deep copy must reproduce the same structure with new nodes.head = [[1,1],[2,1]]→[[1,1],[2,1]]— Both nodes' random pointers target index 1 (the second node).head = []→[]— Empty list copies to an empty list (null).
- · 0 <= n <= 1000
- · -10^4 <= Node.val <= 10^4
- · Node.random is null or points to a node in the list
- · The returned list must share no node objects with the input list