Copying linked list with random pointers

Problem

Having a home defined linked list with the following structure, where the next will point to the node in the list and the random will point to a random node in the list.
Create a copy of the structure(the data field in each node is not unique for different nodes.

As shown Figure 1 and Figure 2, adding an duplicate node between existing nodes in the list can be done in O(N) time.

Figure 1. Original linked list

Figure 2. After adding duplicate nodes.

After that, we need to duplicate the random pointer. Since we added the duplicate node after the original node. new random pointer can be obtained as blow: Assume that we keep the pointer to the original node in prev pointer.

  new_node->random =  prev->random->next;

This process can also take O(N) time.

Lastly, we now have complete two lists. Only thing left is disconnect the list into two lists.

By keeping the pointer two the next node and next prev node as we go through the list, we can disconnect the list into two list.

The root of the new list will root->next and can be stored in advance to be returned. This part takes another O(N).

Here is the code running in O(N), where N is the number of nodes in the linked list