Copy a List With Random Pointers

You are given head, the first node of a linked list. Every node has three fields:

• val — an integer,
• next — the next node, or null at the end,
• random — any node of this same list (it can be the node itself), or null.

Return a deep copy of the list: a new list built from new nodes, one new node for each original node. In the copy, each node has the same val as its original, and its next and random point to the copies of the nodes the original pointed to. No pointer in the copy may point to an original node.

How the input is shown

Each node is shown as [val, randomIndex], from head to tail. randomIndex is the position (counting from 0) of the node that random points to, or null. For example, [[4, null], [9, 0]] is the list 4 -> 9, where the random pointer of 9 points to 4. An empty list is []. Your returned copy is shown in the same way.

Note

• Two nodes can have the same value, so you cannot find a node by its value.
• If the list is empty, return null.
• Hint: walk the list once and make a copy of every node, storing original -> copy in a map. Walk it a second time and set each copy's next and random by looking up the map.