Question: There is a doubly linked list with next pointer and random pointer (points to an arbitrary node in list). You have to make a copy of the linked list and return. In the end original list shouldn't be modified. Time complexity should be O(n).

Modified structure:

class list{
public:
    int val;
    list* next;
    list* random;
};


Example: In below figure BLUE arrows show next pointer while RED arrows show random pointer.



Answer:

1) Create the copy of every node in the list and insert it in original list between current and next node.
  • create the copy of A and insert it between A & B..
  • create the copy of B and insert it between B & C..
  • Continue in this fashion, add the copy of N to Nth node.
As a result of this exercise, we will get a list like shown below:



2) Now copy the arbitrary link in this fashion

original->next->random = original->random->next;
/*Traverse two nodes in every iteration*/

This works because original->next is nothing but copy of original and Original->random->next is nothing but copy of random.

3) Now restore the original and copy linked lists in this fashion in a single loop.
original->next = original->next->next;
copy->next = copy->next->next;

While doing this, take care of end of list (NULL pointer) and NULL pointer dereference.

So in this manner, we are copying the list in O(n) time and O(1) space complexity.

Code:

list* copy_list(list* root)
{
    list *res;
    
    list* cur = root;
    list *next, *tmp;
    
    //Create the copy of every node in the list and insert 
    //it in original list between current and next node. 
    while(cur)
    {
        tmp = new(list);
        tmp->val = cur->val;
        tmp->random = NULL;
        tmp->next = cur->next;
        next = cur->next;
        cur->next = tmp;
        cur = next;        
    }
      
    //save result pointer    
    res = root->next;
    
    //Copy the arbitrary link for result
    cur = root;    
    while(cur)
    {
        cur->next->random = cur->random->next;
        cur = cur->next->next;  //move 2 nodes at a time
    }
    
    //restore the original and copy linked lists
    cur = root;    
    tmp = root->next;
    while(cur && tmp)
    {
        cur->next = cur->next->next;
        cur = cur->next;
        if (tmp->next){
            tmp->next = tmp->next->next;
            tmp = tmp->next;
        }        
    }
    
    return res;
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.