**Intuition**

We are given the head of the list to start with, but there is no pattern to where node.random might point. It could point to null, a previous node, a later node, or even node itself. So if we're going to do this in linear time, we need to use some space.

**Details**

The Java solution below depends on the fact that Java Objects by default have unique values for obj.hashCode() (where possible). A C/C++ solution could instead use the address of a node instead as its "hash".

- Before each recursive call, an entry of ([pointer to original node], [pointer to copy of node]) is added to a "global" HashMap. Since a call is made for every original node, after the recursive call returns, this Map is guaranteed to know the way from any original node to its copy.
- Then, the recursive call is made on node.next, and copy.next is set to the return value of the recursive call.
- Finally, after the recursive call, copy.random is set using the Map's entry for node.random, and copy is returned.

**Java Solution**

```
public class Solution {
Map<RandomListNode, RandomListNode> origToCopy = new HashMap<>();
public RandomListNode copyRandomList(RandomListNode orig) {
if (orig == null) return null;
RandomListNode copy = new RandomListNode(orig.label);
origToCopy.put(orig, copy);
copy.next = copyRandomList(orig.next);
copy.random = orig.random == null ? null : origToCopy.get(orig.random);
return copy;
}
}
```

**Complexity Analysis**

- Time Complexity: O(n), where n is the number of nodes in the linked list.
- This should be clear from the fact that copyRandomList is called exactly once for every node in the list, while all other operations take [amortized, in the case of the HashMap] constant time.

- Space Complexity: O(n). Specifically, about the space taken by n RandomListNode pointer keys and n pointer values in a HashMap.