## 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

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 :)

• Do you want a theoretical solution with guaranteed worst-case running time and a deterministic algorithm? Or do you want a practical solution?
– D.W.
Jan 30 at 4:08
• @D.W. I am interested in any solution :). Although initially I thought of theoretical solutions Jan 30 at 7:07

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.
• Neat, but wouldn't we need extra memory for the hashtable, in addition to "$N$ cells for allocating a new list + $O(1)$"? Jan 30 at 9:35