Description: You are given a pointer to a linked list(struct node*original)whose each node consists of two pointers, a next pointer and an arbitrary pointer. The next pointer points to the next node just like a singly linked list whereas the arbitrary pointer can point to any other node in the linked list. Your task is to make a copy of this linked list using constant extra space.

 

If video does not load, Click here

 

Algorithm:

Loop through the Linked List for each of the following steps and repeat for each node:

1)  Create a copy of each node and insert it in between the present and next node.

2)  Now copy the arbitrary link as:

•       original->next->arbitrary = original->arbitrary->next;

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;

   4) Finally make sure that last element of original->next is NULL.

   C Implementation:  

 
/* Linked List node Structure */
struct node
{     int data;
    struct node* arbit;
    struct node* next; };  
 
/* function to create a new Node */
struct node *newNode(int data)
{     struct node *new_node = (struct node *) malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = NULL;  
   new_node->arbit = NULL;
    return new_node; }
 
/* Function to copy the Linked List */
struct node* copyList(struct node*original)
{
    struct node *copy=NULL ,*original_l, *copy_l,*temp ;
    original_l =original ;
/*  
Loop through the Linked List for each of the following steps and repeat for each node:
1)  Create a copy of each node and insert it in between the present and next node.
*/
    while(original_l !=NULL)
    {
       temp=original_l->next;
       struct node* newnode =newNode(original_l->data);
       newnode->next=temp;
       original_l->next=newnode;
       original_l=temp;
    }
    copy=original->next;
    copy_i=copy;
    original_l=original;
/*
2)  Now copy the arbitrary link as:
•       original->next->arbitrary = original->arbitrary->next;
*/
    while(original_l!=NULL)
    {
        copy_l->arbit=original_l->arbit->next;
        if(copy_l->next!=NULL)
        copy_l=copy_l->next->next;
        original_l=original_l->next->next;
    }
    copy_l=copy;
    original_l=original;
 
/* 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(original_l!=NULL)
    {
        original_l->next=original_l->next->next;
        if(copy_l->next!=NULL)
        copy_l->next=copy_l->next->next;
        original_l= original_l->next;
        copy_l= copy_l->next;
    }
    return copy;
}  

 

Time Complexity:

   O(n)

 
Go to top