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.
- 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
let’s see how it works
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
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.