Clone a linked list with next and random pointer

clone a linked list with next and random pointer

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:

clone a linked list
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:

clone a linked list
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Another Example 3:

clone a linked list
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.

clone a linked list

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,

clone a linked list

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.

clone a linked list

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

clone a linked list

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.

clone a linked list with next and random pointera
clone a linked list with next and random pointera
clone a linked list with next and random pointer

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.

clone a linked list with next and random pointera

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.

clone a linked list with next and random pointera

What is the purpose of using hash-map ?

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

clone a linked list with next and random pointera

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

Tagged : /

Leave a Reply

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