Archive for the ‘data structures’ Category

Consider a doubly linked list whose structure of the node looks like this:

struct node
 struct node *arbitrary; /* can point to any node, including self or NULL */
 int data;
 struct node *next;      /* always points to the next node */

The next pointer points to its immediate next node, unless it is the last node, which obviously points to NULL. The arbitrary node can point to any other node in the list, including itself or NULL. We need to create a clone of the original doubly linked list – this will mean, the clone should preserve the structure / connectivity of the original, as well as the data.

Upon trying to understand the problem and to start thinking about the solution, we might initially feel an O(n) solution is not possible, or we might need to use a Hash data structure, and all such strange thoughts. The arbitrary field of first node can point to last node, the last node’s arbitrary can point to second node. How to bookkeep such information? The length of the list can be thousand or million or more.

So, this problem need to be solved without using temporary variables / arrays, and should run in time polynomial to length of list, ie. with space complexity O(1) and time complexity O(n).