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