Table of Contents
Introduction
In this article, we will discuss a very interesting problem – Clone a linked list with next and 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 we can improve time and space complexities to move towards a more optimised 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.
Let’s see the 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 –
Please try to solve the problem on your own here before moving on to the explanations. It will help you to build your understanding of the problem.
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;
}
};
// defining linked list class
class LinkedList
{
public:
Node *head; // Linked list head reference
LinkedList(Node *head) //constructor
{
this->head = head;
}
void push(int data) //function to insert data at the head of linked list
{
Node *node = new Node(data);
node->next = head;
head = node;
}
// Function to print the linked list
void print()
{
Node *temp = head;
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;
}
LinkedList *clone() //function to return the clone of linked list
{
Node *origCurr = head;
Node *cloneCurr = NULL;
// Hash map which contains node
// to node mapping of original
// and clone linked list.
unordered_map<Node *, Node *> mymap;
// Traverse the original list and
// make a copy of that in the
// clone linked list.
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
origCurr = head;
// 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;
}
// return the head of the clone of linked list which is mymap[head]
return new LinkedList(mymap[head]);
}
};
// main code to test the above implementation
int main()
{
Node *head = new Node(10); // create new head node having value 5
// creating a new linked list with the head node as head
LinkedList *mylist = new LinkedList(head);
//adding more nodes in the linked list using push() function of LinkedList class
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
mylist->head->random = mylist->head->next->next;
//random field of second node i.e. head->next
mylist->head->next->random = mylist->head;
//random field of third node i.e. head->next->next
mylist->head->next->next->random =
mylist->head->next->next->next->next;
//random field of fourth node i.e. head->next->next->next
mylist->head->next->next->next->random =
mylist->head->next->next->next->next;
//random field of fifth node i.e. head->next->next->next->next
mylist->head->next->next->next->next->random =
mylist->head->next;
LinkedList *clone = mylist->clone(); //creating clone of linked list
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 list is the original list and the second one is the clone of the linked list which 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;
}
};
// defining linked list class
class LinkedList
{
public:
Node *head; // Linked list head reference
LinkedList(Node *head) //constructor
{
this->head = head;
}
void push(int data) /*function to insert data at the head of the linked list*/
{
Node *node = new Node(data);
node->next = head;
head = node;
}
// Function to print the linked list
void print()
{
Node *temp = head;
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;
}
LinkedList *clone() //function to return the clone of linked list
{
Node *origCurr = head;
Node *cloneCurr = NULL;
Node *temp = head;
//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*/
}
origCurr = head;
//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;
}
cloneCurr = head->next; //start of clone of the linked list
origCurr = head; //start of original list
LinkedList *clone = new LinkedList(cloneCurr);
//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 */
/* creating a new linked list with the head node as head */
LinkedList *mylist = new LinkedList(head);
/*adding more nodes in the linked list using push() function of LinkedList class*/
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*/
mylist->head->random = mylist->head->next->next;
/*random field of second node i.e. head->next*/
mylist->head->next->random = mylist->head;
/*random field of third node i.e. head->next->next*/
mylist->head->next->next->random =
mylist->head->next->next->next->next;
/*random field of fourth node i.e. head->next->next->next*/
mylist->head->next->next->next->random =
mylist->head->next->next->next->next;
/*random field of fifth node i.e. head->next->next->next->next*/
mylist->head->next->next->next->next->random =
mylist->head->next;
LinkedList *clone = mylist->clone(); //creating clone of linked list
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, to 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.
Frequently Asked Questions
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.
You can see this article related to Multiply Linked Lists and also practice to check your understanding.
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.
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.
Key Takeaways
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.
You should not stop here. There are many interesting problems related to linked list like Merging two sorted linked lists, Print Linked List in reverse order, Count inversion, Add 1 to a linked list, Check linked list palindrome.
Practising makes the concepts more clear and makes you confident about your problem-solving skills.
Do check out CodeStudio to practice commonly asked interview questions to ace your next technical interview.
By: Yukti Kumari
