Clone a linked list with next and random pointer with O(1) space complexity.

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

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.

2.Now we will perform this

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

let’s see how it works

1st Node

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

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

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

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

Two separate lists copied and original list

Original Linked List

Copied Linked list

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.