clone a link list

Clone a link list with next and random Pointer (Part II)

In the previous post, we have already discussed the map-based solution of the problem clone a link list with next and random pointer.

The map-based solution took O(n) extra space but in this post, we will discuss constant space complexity based solutions.

NOTE: The space required for creating a new link list is not considered under space complexity because it is part of the problem. For constant space complexity, you cannot take any further extra space.

Now let us understand the constant space complexity approach.

Problem with the Previous Solution

If you remember the map based solution, for the first part of the problem, for assigning data and next Pointer to the nodes of the new linklist we actually didn’t use the map as all.

The only purpose of the hash-map was to assign random pointers to the nodes of new linklist. Isn’t it ?

What was the actual role of the hash-map in our previous solution ?

If you understand this part, it will be easy for you to crack constant space complexity solution. Let’s understand this part clearly.

We will take the same example from the previous post,

CLONE A LINK LIST

This was the example we used, here we already have the information about the random pointer of nodes of the original linklist.

Also we know which node in original linklist corresponds to which node in new linklist and we were getting this information via hash-map.

Hash-map actually stores the resemblance of nodes of both the linklist. Isn’t it ?

So it’s like we have two information and from there we are finding the third information.

Do we really need a hash-map to store the resemblance ?

Can’t we get this information without using a hash-map ?

The basic idea to this approach is that we already know that total number of nodes in both original and new linklist will be same.

And it’s obvious that first node of original linklist resembles to first node of new linklist, second to second and it goes on.

We will use this information for our constant space based solution.

Idea behind Efficient Solution

CLONE A LINK LIST

The first one is the original linklist and the second one is the cloned linklist.

We will first point the next pointers of the nodes of original linklist to its corresponding node in the new linklist.

At the same time we will point the random pointers of the node of new linklist to its corresponding node in original linklist.

CLONE A LINK LIST

This transformation will help us finding the random pointers of nodes of new linklist.

First let’s discuss how we will convert the linklists to the above form.

We had already assigned data and next pointers to the nodes of new linklist.

Let’s see the code to transform the linklist,

Node *ptr = set_data_and_next_pointers(head);

Node *x = head;
Node *y = ptr;

while(x != NULL)
{
     Node *next_node = x->next;

     y->random = x;
     x->next = y;

     x = next_node;
     y = y->next;
}

‘ptr’ stores address of head of new linklist.

We will make a copy of both the head pointers so that we can keep the address of original head node of both linklists.

Let say ‘x’ stores address of head of original linklist and ‘y’ stores address of head of new linklist.

Now we will run a loop until (x != NULL) and according we will transform both the linklist.

Let us understand it by an example,

CLONE A LINK LIST
Node *next_node = x->next;
Here we store the address of next pointer of 'x' in next_node variable.

y->random = x;
x->next = y;
Here we set random pointer of 'y' to node 'x'. Also we set next pointer of 'x' to node 'y'.

x = next_node;
y = y->next;
At last we move ahead to transform the random and next pointer of next nodes.

This way we will move ahead and transform both the linklist, hope above code is clear to you all.

Why we did the above transformation ?

Now the questions arises, why we did the above transformation. The reason is hidden in the above pictorial diagram.

The idea behind the transformation is that now we can easily get the information of random pointers for the nodes of new linklist.

Let’s see how,

CLONE A LINK LIST

What will be address of the random pointer with node 4 ?

Let say node 4 is denoted by ‘y’, then (y->prev->prev->next) will give us that information about random pointer.

Yes, this is the masterstroke logic behind this algorithm. Now we can get the information about previous node in just O(1) time complexity.

We will run a loop from head pointer of new linklist till it becomes NULL and update the random pointers accordingly.

The code snippet will be,

y = ptr;
while(y != NULL)
{
     if(y->random->random == NULL) {
             y->random = NULL;
    }
    else 
    {
            y->random = y->random->random->next;
     }
     y = y->next;
}

Hope, you understood the above code, one extra condition we give there if random pointer of nodes of original linklist is NULL, then (y->random) will also be NULL. That’s it.

Hope above code and logic behind it is clear to you all.

Time Complexity : O(n)
Space Complexity : O(1)


Yes we didn’t use any extra space for creating new linklist instead we did some transformation and got the result.

Code in C/C++

Node* set_data_and_next_pointers(Node* head) 
{
    if(head == NULL) return NULL;

    Node* newhead=new Node(head->val);
    newhead->next = copyRandomList(head->next);

    return newhead;
}

Node *copyRandomList(Node *head) {

    if(head == NULL) return NULL;

    Node *ptr = set_data_and_next_pointers(head);

    Node *x = head;
    Node *y = ptr;

    while(x != NULL)
    {
         Node *next_head = x->next;

         y->random = x;
         x->next = y;

         x = next_head;
         y = y->next;
    }

     y = ptr;

     while(y != NULL)
     {
         if(y->random->random == NULL) y->random = NULL;
         else y->random = y->random->random->next;
         y = y->next;
     }

     return ptr;
}

I hope the above explanation for Clone a link list with next and random Pointer is clear to you all.

That’s all folks..!!!

Abhishek is currently pursuing CSE from Heritage Institute of Technology, Kolkata. He has a great interest in Data Structures and Algorithms, C++, Language, Competitive Coding, Android Development. His hobbies are Learning new skills, Content Writing, Competitive Coding, Teaching contents to Beginners.

2 Comments

Leave a Comment

Your email address will not be published. Required fields are marked *