LeetCode Q138: Copy List with Random Pointer (hard)

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Solution:

The question is not that hard if you really take care of the node that random pointer pointing to. Basically, there are two ways of doing this. First, we pre-allocate memory for node pointed by random pointer and save them to a hash table. When access to each node, check whether the node has been created ahead or not. Another way is much simpler, we do this in two passes scan of the linklist. In first scan, we just build up entire linklist by linking next pointer and hash each new node with its corresponding node in old linklist. In second pass, we take care of nodes pointed by random pointer.

Method 1:

Method 2:

Round 2 solution:
Using recursion. The solution is very similar to Q133 Clone Graph.