1.
Introduction
2.
Problem Statement
3.
Approach 1
4.
Approach 2 (clone a linked list with next and random pointer in O(1) space)
5.
5.1.
What is a deep copy in a linked list?
5.2.
How do you multiply two linked lists?
5.3.
5.4.
6.
Conclusion
Last Updated: Mar 27, 2024
Hard

# Clone a Linked List with Next and Random Pointer

Yukti Kumari
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction

In this article, we will discuss a fascinating problem - Cloning a linked list with the following and a random pointer. There are problems where you need to clone a singly linked list or a Doubly Linked List, but this one is a bit different and tricky from these traditional questions. We will discuss various approaches to solve this problem and see how to improve time and space complexities to move towards a more optimized version.

In this, the linked list consists of nodes, and each node has two pointers. One of the pointers points to the next node, and it is called the Next pointer.  The other pointer can point to any node present in the list or can be null, and hence we refer to it as a random pointer.

## Problem Statement

Given a linked list in which every node has two pointers. One of the pointers points to the next node, and it is called the Next pointer. The other pointer can point to any node present in the list or can be null, and hence we refer to it as a random pointer.

Create a clone of this linked list and return its head. Note that we have to create a deep copy of the linked list.

Example -

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Approach 1

Forget about the random pointers and think that if the question had been to clone a normal singly linked list, what would our approach have been?

We would then simply traverse the given list, and for each node in the original list, create a new node in the clone and set up the pointers correctly.

Here, also, we will do the same in the first step. i.e., clone the linked list with the next pointers without caring about the random pointers.

Next, we create a hashmap. The key of the hashmap is an original node, and its corresponding value is the new node that we create while iterating the original list.

In the second iteration over the original list,  we clone the random pointer using this relation -

cloned_node -> random =  map[original_node -> random]

where map[original_node -> random] is the node in the cloned list corresponding to the node original_node->random in the original list.
C++ Implementation:

//C++ code to clone a linked list with next and random pointer using hashmap
#include <bits/stdc++.h>
using namespace std;

//defining Linked List Node class which has three fields - data, next and random
class Node
{
public:
int data; //Node data

// Next and random pointers
Node *next, *random;

Node(int data) //constructor
{
this->data = data;
this->next = this->random = NULL;
}
};

{
public:

{
}

void push(int data) //function to insert data at the head of linked list
{
Node *node = new Node(data);
}

// Function to print the linked list
void print()
{
while (temp != NULL)
{
Node *random = temp->random;
int randomData = (random != NULL) ? random->data : -1;
cout << "Node Value = " << temp->data
<< ", ";
cout << "Node Value of the Random pointer = " << randomData << endl;
temp = temp->next;
}
cout << endl;
}

{
Node *cloneCurr = NULL;

// Hash map which contains node
// to node mapping of original
unordered_map<Node *, Node *> mymap;

// Traverse the original list and
// make a copy of that in the
while (origCurr != NULL) //loop terminating condition
{
cloneCurr = new Node(origCurr->data);
mymap[origCurr] = cloneCurr;
origCurr = origCurr->next; //update origCurr to point to the  next node
}

//update origCurr to point to the head of original list for second traversal

// Traversal of original list again
// to adjust the next and random
// references of clone list using
// hash map
while (origCurr != NULL)
{
cloneCurr = mymap[origCurr];
cloneCurr->next = mymap[origCurr->next];
cloneCurr->random = mymap[origCurr->random];
origCurr = origCurr->next;
}

}
};

// main code to test the above implementation
int main()
{
Node *head = new Node(10); // create new head node having value 5

mylist->push(12);
mylist->push(4);
mylist->push(5);
mylist->push(1);

// intialising the values of random pointers of each node of the mylist

//random field of first node i.e. head

//random field of second node i.e. head->next

//random field of third node i.e. head->next->next

//random field of fourth node i.e. head->next->next->next

//random field of fifth node i.e. head->next->next->next->next

cout << "The Original linked list is as follows:\n";
mylist->print();
cout << "\nClone of linked list is as follows:\n";
clone->print();
}

Output:

The Original linked list is as follows:
Node Value = 1, Node Value of the Random pointer = 4
Node Value = 5, Node Value of the Random pointer = 1
Node Value = 4, Node Value of the Random pointer = 10
Node Value = 12, Node Value of the Random pointer = 10
Node Value = 10, Node Value of the Random pointer = 5

Clone of linked list is as follows:
Node Value = 1, Node Value of the Random pointer = 4
Node Value = 5, Node Value of the Random pointer = 1
Node Value = 4, Node Value of the Random pointer = 10
Node Value = 12, Node Value of the Random pointer = 10
Node Value = 10, Node Value of the Random pointer = 5

Time Complexity:

The time complexity of this method is O(n), where n is the number of nodes in the given linked list. Since we traverse the original linked list 2 times to construct the cloned list. Total complexity is  O(n)+O(n) = O(2*n), which is ultimately O(n).

Space Complexity:

We are using a hashmap to map the old list nodes to the new list nodes. Since extra space used is equal to the number of nodes in the list, the space complexity becomes O(n), where n is the number of nodes in the linked list.

## Approach 2 (clone a linked list with next and random pointer in O(1) space)

In the previous approach, we used a hash map which resulted in a space complexity of O(n).

In this approach, we will proceed in the following steps to reduce the space complexity -

• Create a copy of Node1 and insert it between Node1 and Node2 in the original linked list itself. Similarly, create a copy of Node 2 and insert it between Node 2 and Node 3 in the original linked list. Repeat this process for all the nodes. In general, insert a copy of the Node-i between Node_i and Node_i+1. For the last node, insert its copy after it. Now, for all the nodes of the original list - original->next = cloned_node
• In this step, we will set the random pointers of each cloned node in this way - (original->next)->random = (original->random)->next because original->next is nothing but a copy of the original node and (original->random)->next is nothing but a copy of random.

In this figure, the random pointers of all the copy nodes have been initialized.

• Now, restore the original linked list and clone of the linked list in a single traversal in the following way - original->next = original->next->next

copy->next = copy->next->next

The first is the original list, and the second is the clone of the linked list we just constructed.
C++ Implementation:

/* C++ code implementation to clone a linked list with next and random pointers
using O(1) space
*/
#include <bits/stdc++.h>
using namespace std;

/*defining Linked List Node class which has three fields - data, next and random*/
class Node
{
public:
int data; //Node data

// Next and random pointers
Node *next, *random;

Node(int data) //constructor
{
this->data = data;
this->next = this->random = NULL;
}
};

{
public:

{
}

void push(int data) /*function to insert data at the head of the linked list*/
{
Node *node = new Node(data);
}

// Function to print the linked list
void print()
{
while (temp != NULL)
{
Node *random = temp->random;
int randomData = (random != NULL) ? random->data : -1;
cout << "Node Value = " << temp->data
<< ", ";
cout << "Node Value of the Random Pointer = " << randomData << endl;
temp = temp->next;
}
cout << endl;
}

{

Node *cloneCurr = NULL;

//first pass
while (origCurr)
{
temp = origCurr->next;

//inserting copy node
origCurr->next = new Node(origCurr->data);
origCurr->next->next = temp;
origCurr = temp; /*update origCurr to point to the next original node*/
}

//second pass
while (origCurr)
{
if (origCurr->next)
{
/*first check if origCurr->random is Null or not, and then assign value to random*/
origCurr->next->random = origCurr->random ? origCurr->random->next : origCurr->random;
}

/*check if origCurr->next exists or it is NULL
*when origCurr->next is NULL, it implies we have reached end of the list
*else update origCurr to point to next original node in the list
*/
origCurr = origCurr->next ? origCurr->next->next : origCurr->next;
}

origCurr = head;        //start of original list

//third pass
while (origCurr && cloneCurr)
{
origCurr->next = origCurr->next ? origCurr->next->next : origCurr->next;
cloneCurr->next = cloneCurr->next ? cloneCurr->next->next : cloneCurr->next;

origCurr = origCurr->next;
cloneCurr = cloneCurr->next;
}

return clone;
}
};

// main code to test the above implementation
int main()
{
Node *head = new Node(20); /* create new head node having value 5 */

mylist->push(5);
mylist->push(13);
mylist->push(21);
mylist->push(11);

/* initializing the values of random pointers of each node of the mylist*/

/*random field of first node i.e. head*/

/*random field of second node i.e. head->next*/

/*random field of third node i.e. head->next->next*/

/*random field of fourth node i.e. head->next->next->next*/

/*random field of fifth node i.e. head->next->next->next->next*/

cout << "The Original linked list is as follows:\n";
mylist->print();
cout << "\nThe Clone of linked list is as follows:\n";
clone->print();
}

Output:

The Original linked list is as follows:
Node Value = 11, Node Value of the Random Pointer = 13
Node Value = 21, Node Value of the Random Pointer = 11
Node Value = 13, Node Value of the Random Pointer = 20
Node Value = 5, Node Value of the Random Pointer = 20
Node Value = 20, Node Value of the Random Pointer = 21

The Clone of linked list is as follows:
Node Value = 11, Node Value of the Random Pointer = 13
Node Value = 21, Node Value of the Random Pointer = 11
Node Value = 13, Node Value of the Random Pointer = 20
Node Value = 5, Node Value of the Random Pointer = 20
Node Value = 20, Node Value of the Random Pointer = 21

Time Complexity: It is O(n) because in total we make three passes over the entire linked list. The first time, insert a copy of the original nodes after each of them. The second time, to set up the random pointer of the copy nodes correctly. The third time, to separate the original linked list and clone of the linked list. So, total operations are O(3*n) â‹Ť O(n), which is linear complexity.

Space Complexity: It is O(1). Since we donâ€™t use any extra data structure in our algorithm apart from just some variables, it needs only constant space.

Check out this problem - Count Inversions

### What is a deep copy in a linked list?

A deep copy of a linked list means that for every node in the original linked list, we create a new node in the new list and then copy the values of the original node to it. It differs from the shallow copy in which we only copy the references of the nodes of the original linked list.

### How do doubly-linked lists work?

In a doubly-linked list, every node has a data field and two link fields, namely the next pointer and a previous pointer. The next pointer points to the next node in the list, and the previous pointer points to the previous node.

### What is a multi-linked list?

A multi-linked list is a linked list where each node may have pointers to more than one node of the linked list. A doubly-linked list is an example of a multi-linked list that has two-pointers.

## Conclusion

In this article, we learned to solve an interesting version to clone a linked list with next and random pointers. We saw two approaches to solve it. One of the ways was using hashmap to store the old node to new node mapping. But this turned out to be space inefficient. Then, we built up the solution to gain constant space complexity and hence moved to an optimized solution.