4
$\begingroup$

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: enter image description here

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

enter image description here

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

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Neat, but wouldn't we need extra memory for the hashtable, in addition to "$N$ cells for allocating a new list + $O(1)$"? $\endgroup$ Jan 30 at 9:35
  • $\begingroup$ @ZhiltsoffIgor, sure. The question does not list any requirements regarding memory consumption. $\endgroup$
    – D.W.
    Jan 30 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.