Table of Contents

**Leetcode Problem 138**

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. We need to clone-a-linked-list-with-next-and-random-pointer. Read rat in a maze problem here

Return a **deep copy** of the list.Aka clone-a-linked-list-with-next-and-random-pointer.

The Linked List is represented in the input/output as a list of **n** nodes. Each node is represented as a pair of **[val, random_index]** where:

**val**: an integer representing**Node.val****random_index**: the index of the node (range from**0**to**n-1**) where random pointer points to, or**null**if it does not point to any node.

**Example 1:**

Input:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]Output:[[7,null],[13,0],[11,4],[10,2],[1,0]]

**Example 2:**

Input:head = [[1,1],[2,1]]Output:[[1,1],[2,1]]

**Anothe**r **Example 3:**

Input:head = [[3,null],[3,0],[3,null]]Output:[[3,null],[3,0],[3,null]]

**Analysis of Problem Statement**

The problem seems quite confusing and it is but let us understand it clearly. We are basically given a **Linked List** where each nodes have **three** field.

Basically the **structure** of the node of the Linklist will look like,

struct Node { int data; struct Node *next; struct Node *random; };

The node has its data and it also stores two pointers (Next and Random). Next Pointer stores the address of Next Node and Random Pointer stores the address of any Random Node, it can be NULL as well.

So, we are given a link list where each node stores this information. Our task is to create a new link list which is a copy of the given link list. Learn Two pointer algorithm

**Approach to the Problem**

I hope the Problem Statement is clear to you. This problem is a bit different from other Linklist Problems but doesn’t worry we will understand it step by step.

Our motive is to just create a copy of the given link list.

So, for that, we have to create new nodes.

**How to create new nodes..??**

In C/C++, we create nodes dynamically by using **malloc()** and **new()** keywords.

Normally, we have to **create** a new node of a Node type and we have to assign data to it.

But here GFG has already created the constructor for us, we just have to create a new node and have to pass data as a parameter. Learn Subtree problem in data structure

Node *head = new Node(x->data);

Here we are creating a linklist node of type **‘Node’** and assigning x’s data to it. The next and random will be **NULL** initially as mentioned in the constructor.

**Hash – Map based Approach**

Since we have to **clone/copy** the original linklist, we will definitely need some data structure to store the information of nodes of original linklist.

For that we will use **hash-map** where key will be the nodes of original linklist and value will be the nodes of cloned linklist.

**Assign Data and next Pointer to the new node**

In the first step, for each node in the original linklist we will create a new node with same data and then we will recursively assign its next Pointers.

Let’s understand it clearly with an example,

Suppose this is the original Linklist given to us and we have to cloned it to new Linklist.

Let us give some address to the nodes of original linklist, it will be easy for us to understand.

Now, I will create a new Node and I will assign it’s value to it. Let do it.

This is the new node we created with the same node value. **NOTE** we have not assigned it’s next and random pointer yet and also the address of the new node is different.

Now, we will assign **next** pointer to the new node and for that we will use **recursion**. Let’s see how.

```
Node* copyRandomList(Node* head)
{
if(head == NULL) return NULL;
Node* newhead=new Node(head->val);
newhead->next = copyRandomList(head->next);
return newhead;
}
```

This is how** recursive **function will work. Here we have only assigned next pointer to the cloned linklist.

The **pictorial** diagram below make recursion more clear.

Nodes of **cloned linklist** will be created for every nodes of original linklist and at the same time we are actually assigning the next pointer of **previous node** to the **current node** of the new linklist.

If you are unable to understand the above, take a pen paper and dry run on it.

**Assign random Pointer to the new node**

We have already assigned the data values and next pointers to the nodes of new linklist. Now, we have to assigned the **random pointer** to it with respect to original linklist.

Since random pointers are **random**, so here we will need a data structure to store the random pointers of **original linklist** and accordingly we will assign the random pointer to the nodes of new linklist.

For this purpose we will use **hash-map**, let see how it will help us.

We will use the same example,

We will first create a **hash-map** where key will be the nodes of original linklist and value will be the nodes of cloned linklist.

**What is the purpose of using hash-map ?**

Let us understand what we need a **hasp-map** here.

**Random Pointer** of address **275** is **425** in the original linklist as mentioned in the diagram.

Value of the map with key **275** is **900**. It means node with address **275** of original linklist **corresponds** to node with address** 900** in new linklist.

Now, we know random pointer of **275** is **425**, so we will set the random pointer of the node **900** to the value of the map with key **425**.

And here the role of map comes to play. Hash-Map actually stores the **resemblance** of nodes of new linklist with respect to original linklist.

Hope I can able you to understand how we will set the random pointer.

newhead->random = copyRandomList(head->random);

After that we will find the **random** pointer in the map, if found we will return it’s value.

if(m.find(head) != m.end()) return m[head];

Hope this above part is clear to you, let us see the full code.

```
unordered_map<Node*,Node*> m;
Node* copyRandomList(Node* head)
{
if(head == NULL) return NULL;
if(m.find(head) != m.end()) return m[head];
Node* newhead=new Node(head->val);
m[head]=newhead;
newhead->next = copyRandomList(head->next);
newhead->random = copyRandomList(head->random);
return newhead;
}
```

Hope the above code is clear to you. Dry run above code and you will understand it clearly.**Time Complexity : O(n)Space Complexity: O(n)**

Since we are using a hash-map, the space complexity increases to O(n). But can you solve it in

**constant space**?

**NOTE**: The space required for 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.

We will discuss the constant space solution in the next post. Till then try to understand clone-a-linked-list-with-next-and-random-pointer this approach and try to think of the constant space complexity approach as well.

That’s all folks..!!!