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


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