Copy Linked List with Random Pointer

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

struct node* list{  
public:  
    int val;  
    list* next;  
    list* random;  
};  
In below figure BLUE arrows show next pointer while RED arrows show random pointer.

http://www.geeksforgeeks.org/a-linked-list-with-next-and-arbit-pointer/
http://www.geeksforgeeks.org/clone-linked-list-next-arbit-pointer-set-2/

Strategy:
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;
}
Method 2:(Uses O(n) extra space)
This method stores the next and arbitrary mappings (of original list) in an array first, then modifies the original Linked List (to create copy), creates a copy. And finally restores the original list.
1) Create all nodes in copy linked list using next pointers.
3) Store the node and its next pointer mappings of original linked list.
3) Change next pointer of all nodes in original linked list to point to the corresponding node in copy linked list.
Following diagram shows status of both Linked Lists after above 3 steps. The red arrow shows arbit pointers and black arrow shows next pointers.

Figure 2

4) Change the arbit pointer of all nodes in copy linked list to point to corresponding node in original linked list.
5) Now construct the arbit pointer in copy linked list as below and restore the next pointer of nodes in the original linked list.

       copy_list_node->arbit =
                      copy_list_node->arbit->arbit->next;
       copy_list_node = copy_list_node->next; 

6) Restore the next pointers in original linked list from the stored mappings(in step 2).
Time Complexity:  O(n)
Auxiliary Space:  O(n)

Copy a Singly Linked List
copy_linked_lists(struct node *q, struct node **s)
{
    if(q!=NULL)
    {
        *s=malloc(sizeof(struct node));
        (*s)->data=q->data;
        (*s)->link=NULL;
        copy_linked_list(q->link, &((*s)->link));
    }
}