Copying a linked list with additional arrows from each node

Question

Statement

Consider the following modified node structure for the linked list:

struct Node {
   int value;
   Node* next;
   Node* random;
}

The next field points to the next element in the list. The random field points to some other node, which is guaranteed to be in the same list. E.g. (black arrows denote next, purple - random): Copy this list preserving the structure of arrows (time: $O(N)$, memory: $N$ cells for allocating a new list + $O(1)$)

(Unsatisfactory) Solution

I came up with the following solution (I will explain what bothers me about it further):

Let's allocate $N$ cells for the new list "in-between" the nodes of the initial list, i.e. we insert the first cell, which will eventually end up in the new list, between the first and the second cells of the initial list; the second cell - between the second and the third; and so on... Thus, we get something like this:

Now, we can copy the structure of random arrows. We simply start traversing the list following the rule (keep in mind, black and blue nodes constantly alternate):

• whenever we enter a black node N, we find R := N->random->next, i.e. we store the node that succeeds the destination of the purple arrow pointing from the current node.
• whenever we enter a blue node M, we simply set M->random := R, that is assign the random field to be the R, acquired on the previous step.

Intuitively, I would draw this process like this (as physicist may put it, orange arrows denote "distance", purple ones - the "displacement"):

And then we split this list into two (black and blue) in an additional third traverse. Voila!

Question

What I dislike about this solution:

1. It does not work if the initial list is read-only
2. It uses 3 traverses, instead of just 1

So, my questions are:

1. Is there a way to do the same for a read-only list?
2. Is there a way to do the same in a single traverse?
3. Is there a way to do the same for a read-only list in a single traverse?

I would appreciate hints instead of full solutions :)

Answer 1

A very simple approach is to build up a hashtable that maps from the address of the original node to the copied node. Then, it is easy to copy the entire linked list. A single linear traversal of the list suffices, and the link can be read-only.

From a theoretical perspective, the expected running time is $O(n)$ if you use a good enough hash function (e.g., a 2-universal hash), though the worst-case time could be $O(n^2)$. From a practical perspective, you can expect $O(n)$ performance in practice if you have a good hash function.