Copy List with Random Pointer

You get the head of a linked list. Build a deep copy of it and return the copy's head.

Each node has a value, a next pointer and one more pointer, random. This random pointer can lead to any node of the list, even the node itself. It can also be nil.

The copy is made only of new nodes, one for each original node, with the same values. In the copy, each next and random leads to the matching new node. Nothing points back into the original list.

Say an original node's random leads to the third node. Then its copy's random leads to the copy of the third node.

The examples describe the list with two arrays of the same length. The first, values, holds the values from the head on. The second, random, holds one entry per node. For node i, random[i] is the index of the node its random leads to. Indexes start at 0, and nil means no node.

Your function gets only head.

Example 1:

Input: values = [4,9,1,6], random = [nil,3,0,2]
Output: values = [4,9,1,6], random = [nil,3,0,2]
Explanation: The dashed blue arrows are the random pointers.
The copy has four new nodes with the same links:
the new 4's random is nil,
the new 9's random leads to the new 6,
the new 1's random leads to the new 4,
the new 6's random leads to the new 1.

Example 2:

Input: values = [8,8], random = [nil,0]
Output: values = [8,8], random = [nil,0]
Explanation: Both nodes hold 8.
The second 8's random leads to the first 8.
In the copy, it must lead to the new first 8, not the old one.

Example 3:

Input: values = [7], random = [0]
Output: values = [7], random = [0]
Explanation: The only node's random leads to itself.
In the copy, the new node's random leads to the new node.

Constraints:

• 0 to 1,000 nodes.
• For an empty list (head is nil), return nil.
• Each value is from -10,000 to 10,000.
• Each random is nil or leads to a node of the same list.