Cloning a singly linked list

Question

I have a singly linked list. Apart from the normal "Next" pointer, there is one more pointer(random ptr) in each node which points to some random node of the list. How to create a clone of such a list? (In less than O(n^2)).

Any suggestion or solution using Java?

Answer 1

Here is an answer in O(n) time and O(1) space. (Solutions with a hashtable or association map need O(n) space). shg's link is also a solution in O(n) time and O(1) space.

• traverse the list to count the number of cells, n.
• Create an array t of size n, each cell consisting of two pointers a and b. At the end of the algorithm, this will be the copy. But it isn't for now.
• traverse the original list. For the k^th cell c of the original list:
  • let t[k].a be a pointer to c
  • let c.next be a pointer to t[k] (the original list is temporarily destroyed, we will restore it later.). We can now follow pointers back and forth between the original list and t.
• traverse the original list, and for each cell c, let c.next.b be a pointer to c.random.next. (c.next is a cell in t, so is c.random.next). This way, the b fields of the cells in t are a copy of the structure of the random pointers in the original list.
• restore the original list: for each k, let t[k].a.next point to t[k+1].a.next
• make t a linked list: for each k, let t[k].a point to t[k+1].

As opposed to shg's link, this solution has the drawback of requiring a continuous block of size n in memory.

Answer 2

You could clone all the nodes in order and, during this first pass, build an identity map associating each original node with its clone.

Then do a second pass and, for each original node, get its associated random node, then get the corresponding clone from the map, and associate the clone of the original node to the clone of the random node. The whole process would still be O(n).