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.

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