# Java Solution

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.