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 None.

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 None means no node.

Your function gets only head.

Example 1:

Input: values = [4,9,1,6], random = [None,3,0,2]
Output: values = [4,9,1,6], random = [None,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 None,
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 = [None,0]
Output: values = [8,8], random = [None,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 None), return None.
• Each value is from -10,000 to 10,000.
• Each random is None or leads to a node of the same list.