Create a duplicate copy of Linked list in O(n) time

Question

A link list is given with two pointer, 1st is pointing to next node and another is random pointer. Random pointer is pointing to any node of LinkedList. Write a complete program to create a copy of Linked List(c,c++,c#), without changing original list and in O(n).

I was asked this question in one of the interviews and I could not figure out the solution. Help would be appreciated.

Answer 1

Copying a normal linked list in linear time is obviously trivial. The only part that makes this interesting is the "random" pointer. Presumably by "random" you really mean that it points to another randomly chosen node in the same linked list. Presumably, the intent is that the copy of the linked list re-create exactly the same structure -- i.e., the 'next' pointers create a linear list, and the other pointers refer to the same relative nodes (e.g., if the random pointer in the first node of the original list pointed to the fifth node in the original list, then the random pointer in the duplicate list would also point to the fifth node of the duplicate list.

Doing this in N² time is fairly easy. First duplicate the list normally, ignoring the random pointer. Then walk through the original list one node at a time, and for each node walk through the list again, to find which node of the list the random pointer referred to (i.e., how many nodes you traverse via the next pointers to find a next pointer holding the same address as the random pointer of the current node. Then walk through the duplicate list and reverse that -- find the N^th node's address, and put that into the current node's random pointer.

The reason this is O(N²) is primarily those linear searches for the right nodes. To get O(N), those searches need to be done with constant complexity instead of linear complexity.

The obvious way to do that would be to build a hash table mapping the address of each node in the original list to the position of that node in the list. Then we can build an array holding the addresses of the nodes in the new list.

With those, fixing up the random pointers is pretty easy. First, we walk through the original list via the next pointers, duplicating the nodes, and building our new list connected via the next pointers, but leaving the random pointers alone. As we do that, we insert the address and position of each node into the hash table, and the address of each node in the new list into our array.

When we're done with that, we walk through the old list and new list in lock-step. For each node in the old list, we look at the address in that node's random pointer. We look up the position associated with that address in our hash table, then get the address of the node in the new list at that position, and put it into the random pointer of the current node of the new list. Then we advance to the next node in both the old and new lists.

When we're done, we throw away/destroy both the hash table and the array, since our new list now duplicates the structure of the old one, and we don't need the extra data any more.