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

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

Clarifying edit:

The following works only if the "random" pointers are unique, as BowieOwens pointed out.
I'm leaving the answer just for the general idea, but please don't upvote as it's most definitely wrong.

---

If I'm not entirely mistaken, you can do this without using any extra storage.

As you're copying the old list, store the random pointer from the old node in the random pointer of the new node.
Then, set the random pointer of the old node to point at the new node.

This will give you a "zig-zag" structure between the old list and the new list.

Pseudocode:

Node* old_node = <whatever>;
Node * new_node = new Node;
new_node->random = old_node->random;
old_node->random = new_node;

Once you've copied the old list like that, you start over, but replace the random pointers like this, restoring the pointers in the old list while setting the random pointers in the new list to the corresponding new nodes:

Node* old_random = old_node->random->random; // old list -> new list -> old list
Node* new_random = new_node->random->random; // new list -> old list -> new list
old_node->random = old_random;
new_node->random = new_random;

It looks much better on paper, but I'm afraid my ASCII art skills aren't up to it.

This does change the original list, but it's restored to the original state.
Whether that's permissible depends on the interview, I guess.

Answer 2

As you should know, O(n) means linear. As you need a copy of a linear data structure, you will not have problems with it, since you just need to iterate over the nodes of the original list and for each visited node you will create a new node for the new list. I think that the question is not well formulated, because you need to know some aspects to do the job as: this is a circular implementation? What is the "next" node? The next node of a node or the 1st node of the list? How the list ends?

Answer 3

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.

Answer 4

Maybe this question is a trick, to test how you answer for strange question, because it's just very simple :

1) Iterate to each node

2) Create new node for other linked list, and copy value.

The cost is always O(n) : because you just iterate to whole linked list for 1 time only !!!

Or, you have understand something wrong on his question.

Answer 5

Overview of the approach
We won't try to create a new linked list right from the word go. Duplicate the items in the original linked list first, then split the list into 2 identical lists.

The details
Step 1 : Run through the linked list using the next pointers and create a duplicate of each node.

original :: A -> B -> C -> D -> E ->null

updated :: A -> A' -> B -> B' -> C -> C' -> D -> D' ->E -> E' -> null

This can be easily done in a single loop.

Step 2 : Traverse the list again, and fix the random pointers like this

Node *current= start;
Node *newListNode, *random;
while (current!= null) {
    // If current node has a random pointer say current = A, A.random = D;
    if ( (*current)->random != null ) {
        // newListNode will point to A'
        newListNode = (*current)->next;
        random = (*current)->random;
        random = (*random)->next;
        // Make A' point to D's next, which is D'
        (*newListNode)->random = random;
    }
    // Here A'.random = D'
    // Current goes to the next node in the original list => B , and not A'
    current= (*newListNode)->next;
}

Step 3 :: Split the list into 2 lists. You just need to fix the next pointers here.

Original :: A -> A' -> B -> B' -> C -> C' -> D -> D' ->E -> E' -> null
New :: A -> B -> C -> D -> E ->null
       A' -> B' -> C' -> D' -> E' ->null

Node *start1 = head;
Node *start2 = (*head) ->next      // Please check the boundary conditions yourself,
                                   // I'm assuming that input was a valid list
Node *next, *traverse = start2;
while (traverse != null) {
    next = (*traverse)->next;
    if (next == null) {
        (*traverse)->next = null;
        break;
    }
    (*traverse)->next = (*next)->next;
    traverse = next;
}

This way, you've created a copy of the original list in O(n) time. You traverse the list 3 times, which still is order of n.