We have a double linked list where each node consists of three pointers data, random and next. Now our task is to clone this linked list

 

                                     Image for post

Now let’s look into another solution of this problem.

  1. Create a copy of node 1 and placed it in between 1 and 2, copy of node 2 and place in between 2 and 3 and so on till the nth node.

 

Image for post

2.Now we will perform this

original->next->random= original->random->next;

let’s see how it works

1st Node

 

Image for post

So we can clearly see that 1st copied node random pointer is connected to the 5th copied node which is same as in the original linked list

 

Image for post

We can similarly do it for the rest of the list and will get the following linked list

 

Image for post

3.Now our task is to restore the copied and original linked list which can achieved by this statement

original->next = original->next->next;

copy->next = copy->next->next;

Ensure that original next is null after traversing the whole list

Let’s see it for the 1st node

 

Image for post

After performing this operation for the entire remaining node we will get

Two separate lists copied and original list

Original Linked List

 

                                          Image for post

Copied Linked list

 

                        Image for post

Complexity

Time complexity: It is O (n) as we are traversing through the list once.

Space complexity is O (1) since no additional Space is required

This is the link for the solution to the above problem.

Leave a Reply