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.

Table of Contents

**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,

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**

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**.

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,

Node *next_node = x->next;Here we store the address of next pointer of 'x' innext_nodevariable.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,

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..!!!