Clone a linked structure with two pointers per node

Clone a linked structure with two pointers per node. Suppose that you are given a reference to the first node of a linked structure where each node has two pointers: one pointer to the next node in the sequence (as in a standard singly-linked list) and one pointer to an arbitrary node. Design a linear-time algorithm to create a copy of the doubly-linked structure. You may modify the original linked structure, but you must end up with two copies of the original.

```private class Node {
private String item;
private Node next;
private Node random;
}```

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

There’s a better way at the end (a hint that gives away everything). You can skip my version. It works but not so elegant.

Apparently if this is just a singly-linked list, it would be trivial. But the tricky part is the random node pointer. It points to a node in the list but you don’t know its position in the list. So one way is to traverse from the first node and find at which position the node is the same as one the random pointer points to.

For a brutal force algorithm, we can do the following:

1. Simply clone along the way from the first node to the last node. O(N) time
2. Then start from the first node: for each node, find the position of the node its random pointer points to by traversing the list. Say we call it p, Once found, wire the random pointer of its clone to the node at position p in the clone list. This can take up O(N^2) time.

What’s taking so long is that we have to traverse the list to know the position of the random node, which takes O(N) time. Same for the traverse in the clone list. What if we can speed it up to O(1) time? Again, we want to search something in O(1) time, which reminds me of a Hashtable. And once we have  the position (or the index), we want to wire things up in O(1) time. This reminds me of an array.

So if I’m allowed to use additional data structure, I could do it like the following:

1. Clone the list from the first node. And in the meantime, put each original node and its index from the first node into a Hashtable<Node, Integer>. At the end of this step, we should get a cloned list (incomplete, since the random pointer of the node in this list is still pointing to the node in the original list).
2. Create an array Cloned of the Node with size N (we should know the size of the list from the first step). Put each node in the cloned list to this array one by one.
3. For each node N in the orginal list, get its random node and check it in the Hashtable to get its index i. Then wire N’s clone with Cloned[i].

This is still O(N) time but we are using extra spaces. Let’s move on to the better one.

==============================================================

Now I have no idea how someone comes up with this idea. A bit of hint would be simply inserting each node’s clone right after itself. I hope you see where this is going. Once we are done with the inserting, we can extract the cloned list easily.

==============================================================

Summary:

• If we are doing clones of or making changes to each node, consider keeping the new node in the original list like what happened in this question.
• Search in O(1) time? Think about Hashtable.
• Access somewhere with an index in O(1) time? Well array comes to mind.
• List all these tools down first and think about how to use them.

Code on github: