Given a linked list, in which every node contains the next pointer. They also contain an additional random pointer that points to any random node present in the linked list or a null pointer in the linked list. We have to make a clone of the given Linked list that contains exactly the same number of nodes as well as the same number of pointers pointing to their respective nodes’ position in the original linked list.
Input:
Original Linked List:
Output:
ClonedLinkedList:
7 -> 0
13 -> 7
11 -> 1
10 -> 11
1 -> 7
Explanation:
- The Head node in the linked list is connected to the next and null reference i.e., (7, null).
- The second node in the linked list is connected to the next node and the head node of the linked list (13,7).
- The third node in the linked list is connected to the next node and the last node of the linked list.
- The fourth node is connected to the next node of the linked list and the third node of the linked list.
- The last node is connected to the null node and the first node of the linked list.
Approach 1
- The Algorithm of this approach is Hashing, where we store every node of the linked list as a key and its copy as a value in the HashMap.
- We traverse the given linked list, i.e., Original Linked List, and using a hashmap, we point the next as well as random pointer/reference of the particular node to its required position.
- Then we return the head of the Linked list from the HashMap.
Java Program
//Importing all the required libraries
import java.util.*;
import java.util.Map.Entry;
import java.io.*;
class Main{
//Creating static head Reference
static Node head;
//Creating class of the Node
static class Node{
Node next; //next Reference to the node in the linked list
Node random; //random Reference to the node in the linked list
int data; //data to be stored to the node in the linked list
//Creating Constructor
public Node(int data){
this.data=data; //Storing the data to the node
this.next=null;
this.next=null;
}
}
//Function to Transverse the Linked list
static void Transverse(Node head){
//Checking if the Linked list is null or not
if(head==null) {
return ;
}
//Creating new reference for the head of the Linked list
Node temp_LinkedList=head;
//Transverse the Linked List
while(temp_LinkedList!=null){
//Checking if the random pointer is null or not
if(temp_LinkedList.random!=null){
System.out.println(temp_LinkedList.data+"->"+temp_LinkedList.random.data);
}
else{
System.out.println(temp_LinkedList.data+"->"+0);
}
temp_LinkedList=temp_LinkedList.next;
}
}
static Node clone(Node head){
HashMap<Node,Node>H=new HashMap<Node,Node>();
//Creating Temporary Linked list
Node temp_LinkedList=head;
while(temp_LinkedList!=null){
H.put(temp_LinkedList, new Node(temp_LinkedList.data));
temp_LinkedList=temp_LinkedList.next;
}
//Iterate the Map containing node and its reference
for(Entry<Node,Node>node:H.entrySet()) {
node.getValue().next=H.get(node.getKey().next);
node.getValue().random=H.get(node.getKey().random);
}
//Returning the cloned linked list
return H.get(head);
}
public static void main(String args[]){
//Creating Head of the linked list
head=new Node(10);
//Creating Second node of the linked list
head.next=new Node(11);
//Creating third node of the linked list
head.next.next=new Node(12);
//Creating fourth node of the linked list
head.next.next.next=new Node(13);
//Creating Random reference of the head node to the second node of the linked list.
head.random=head.next;
//Creating Random reference of third node to the second node of the linked list
head.next.next.random=head.next;
//Printing the original linked list
System.out.println("Original LinkedList");
Transverse(head);
//Creating a new line
System.out.println();
//Cloning the linked list
Node clone=clone(head);
System.out.println("Cloned Linkedlist");
//Transversing the Cloned linked list
Transverse(clone);
}
}
Output
Python Program
#Creating node class for the linked list
class Node:
#Creating Constructor
def __init__(self, data):
#Data to be stored in the node
self.data = data
#Next pointer of the node of the Linked list
self.next = None
#Random pointer of the node of the Linked list
self.random = None
#Function for Traversing the Linked list
def transverse(head):
#Checking the base case
if(head==None):
return None
#Transversing the Linked List
while(head != None):
#Checking the Random Reference in the node of the linked list
if(head.random != None):
#If Random Reference Present in the node print
print(head.data,"->",head.random.data)
#Condition if node does not contains random pointer
else:
print(head.data,"-> 0")
#Reference the next node in the linked list
head = head.next
#Function to make clone of the original linked list
def clone(head):
#Creating temporary reference of the linked list
origCurr = head
#Creating map for storting the node and its copy
mymap = {}
#Iterate the original linked list reference
while(origCurr != None):
#Storing the node and its copy in the hash Map
cloneCurr = Node(origCurr.data)
mymap[origCurr] = cloneCurr
origCurr = origCurr.next
origCurr = head
#Iterate the original linked list reference
while(origCurr != None):
cloneCurr = mymap.get(origCurr)
#Pointing the node to its next node
#Pointing the node to its random node
cloneCurr.next = mymap.get(origCurr.next)
cloneCurr.random = mymap.get(origCurr.random)
origCurr = origCurr.next
#Returning the head
return mymap.get(head)
#Creating First node of the linked list
head = Node(10)
#Creating Second node of the linked list
head.next = Node(11)
#Creating Third node of the linked list
head.next.next = Node(12)
#Creating random reference of the First node to its own
head.random = head
#Printing the original Linked list
print("Original Linked list:")
#Transversing the original linked list
transverse(head)
#Printing the clone linked list
print("Clone Linked List")
#Calling function to create a clone of the linked list
clone=clone(head)
#Transversing the Cloned Linked list
transverse(clone)
Output
C++ Program
//Importing all the required libraries
#include
#include
#include<bits/stdc++.h>
using namespace std;
//Creating structure for the node of linked list
struct Node{
int data;//data to be stored to the node in the linked list
Node*random; //random Pointer to the node in the linked list
Node*next;//next reference to the node in the linked list
//Creating Constructor
Node(int data){
this->data=data; //Storing the data to the node
this->next=nullptr;
this->random=nullptr;
}
};
//Function to Transverse the Linked list
void transverse(Node *head){
//Checking if the Linked list is null or not
if(head==NULL){
return;
}
//Transverse the Linked List
while(head!=NULL){
//Checking if the random pointer is null or not
if(head->random!=NULL){
cout<data;
cout<<"->";
cout<random->data;
}
else{
cout<data;
cout<<"-> 0 ";
}
cout<<"\n"; head=head->next;
}
}
void clone(Node *head){
if(head==NULL){
return;
}
//Creating Temporary Linked list
Node *origLinkedList = head;
Node *cloneLinkedList = NULL;
unordered_map<Node*, Node*> mymap_LinkedList;
// Traverse the original list and make a copy in the map.
while (origLinkedList!= NULL)
{
cloneLinkedList = new Node(origLinkedList->data);
mymap_LinkedList[origLinkedList] = cloneLinkedList;
origLinkedList = origLinkedList->next;
}
// Initialize original list again.
origLinkedList = head;
//Iterate the Map containing node and its reference
while ( origLinkedList!= NULL)
{
cloneLinkedList = mymap_LinkedList[ origLinkedList];
cloneLinkedList->next = mymap_LinkedList[ origLinkedList->next];
cloneLinkedList->random = mymap_LinkedList[ origLinkedList->random];
origLinkedList = origLinkedList->next;
}
//Transverse the head of the map
transverse(mymap_LinkedList[head]);
}
int main(){
//Creating Head of the linked list
Node *head =new Node(10);
//Creating Second node of the linked list
head->next=new Node(11);
//Creating third node of the linked list
head->next->next=new Node(12);
//Creating Random reference of the head node to its own node of the linked list.
head->random=head;
printf("Printing original Linked List\n");
transverse(head);
printf("Printing the cloned linked list\n");
clone(head);
return 0;
}
Output
Complexity
- Time Complexity: The Time complexity of this approach is O(n).
- Space Complexity : The Space Complexity of this approach is O(n) because we are using the map data structure in this approach.
Approach 2
This approach is a little tricky, but this approach is the optimized approach to this problem. We can solve this problem in O(n) Time complexity and O(1) Space Complexity.
- Create a copy of every node present in the original linked list and insert it to the adjacent of its parent node.
- In the next step, Copy the random reference/Pointer from the original node and initialize it to the copied node which is adjacent to its parent node.
- Remove all the copied nodes from the original linked list and store them in the clone linked list.
- The clone linked list is the resultant linked list that we want.
Input Linked List (Original Linked List):
First Step:
- Create a copy of every node present in the original linked list and insert it to the adjacent of its parent node.
Second step:
- In this step, Copy the random reference/Pointer from the original node and initialize it to the copied node which is adjacent to its parent node.
Third step:
- Remove all the copied nodes from the original linked list and store them in the clone linked list and make a clone linked list from the copied nodes.
Below is the implementation of the above approach:
Java
import java.util.*;
import java.util.Map.Entry;
import java.io.*;
class Main{
//Creating static head Reference
static Node head;
//Creating class of the Node
static class Node{
Node next; //next Reference to the node in the linked list
Node random; //random Reference to the node in the linked list
int data; //data to be stored to the node in the linked list
//Creating Constructor
public Node(int data){
this.data=data; //Storing the data to the node
this.next=null;
this.next=null;
}
}
//Function to Transverse the Linked list
static void Transverse(Node head){
//Checking if the Linked list is null or not
if(head==null) {
return ;
}
//Creating new reference for the head of the Linked list
Node temp_LinkedList=head;
//Transverse the Linked List
while(temp_LinkedList!=null){
//Checking if the random pointer is null or not
if(temp_LinkedList.random!=null){
System.out.println(temp_LinkedList.data+"->"+temp_LinkedList.random.data);
}
else{
System.out.println(temp_LinkedList.data+"->"+0);
}
temp_LinkedList=temp_LinkedList.next;
}
}
static Node clone(Node head) {
//Creating a new reference of the head
Node original_node=head;
//Creating temporary reference
Node temporary_reference=null;
while(original_node!=null) {
//Inserting copy of node and insert to its adjacent position in the linked list
temporary_reference=original_node.next;
original_node.next=new Node(original_node.data);
original_node.next.next=temporary_reference;
//Update the linkedList
original_node=temporary_reference;
}
//Initialize the head of the Linked list to the original_node
original_node=head;
while(original_node!=null) {
//Adjust the random pointer to the new created copy node in the original linked list
original_node.next.random=(original_node.random!=null)?original_node.random.next:null;
//Update the position of the original Linked list
original_node=original_node.next.next;
}
original_node=head;
//Creating cloning of the linked list
Node clone=head.next;
int count=0;
Node temporary_reference1=clone;
while(clone!=null) {
//Copy the all the nodes from the original linked list
clone.next=clone.next!=null?clone.next.next:clone.next;
clone=clone.next;
}
//Return the cloned linked list
return temporary_reference1;
}
public static void main(String args[]){
//Creating Head of the linked list
head=new Node(10);
//Creating Second node of the linked list
head.next=new Node(11);
//Creating third node of the linked list
head.next.next=new Node(12);
//Creating fourth node of the linked list
head.next.next.next=new Node(13);
//Creating Random reference of the head node to the second node of the linked list.
head.random=head.next;
//Creating Random reference of third node to the second node of the linked list
head.next.next.random=head.next;
//Printing the original linked list
System.out.println("Original LinkedList");
Transverse(head);
//Creating a new line
System.out.println();
//Cloning the linked list
Node clone=clone(head);
System.out.println("Cloned Linkedlist");
//Transversing the Cloned linked list
Transverse(clone);
}
}
Output
Python Program
#Creating node class for the linked list
class Node:
#Creating Constructor
def __init__(self, data):
#Data to be stored in the node
self.data = data
#Next pointer of the node of the Linked list
self.next = None
#Random pointer of the node of the Linked list
self.random = None
#Function for Traversing the Linked list
def transverse(head):
#Checking the base case
if(head==None):
return None
#Traversing the Linked List
while(head != None):
#Checking the Random Reference in the node of the linked list
if(head.random != None):
#If Random Reference Present in the node print
print(head.data,"->",head.random.data)
#Condition if node does not contains random pointer
else:
print(head.data,"-> 0")
#Reference the next node in the linked list
head = head.next
#Function to make clone of the original linked list
def clone(head):
#Creating temporary reference of the linked list
original_node = head
#//Creating temporary reference
temporary_reference=None
#Iterate the original linked list reference
while(original_node != None):
#Inserting copy of node and insert to its adjacent position in the linked list
temporary_reference=original_node.next
original_node.next=Node(original_node.data)
original_node.next.next=temporary_reference
#Update the node
original_node=temporary_reference
original_node=head
while(original_node!=None):
#Adjust the random pointer to the new created copy node in the original linked list
original_node.next.random=original_node.random.next if original_node.random!=None else None
#Update the position of the original Linked list
original_node=original_node.next.next
original_node=head
#Creating cloning of the linked list
clone=head.next
temporary_reference1=clone
while(clone!=None):
#Copy the all the nodes from the original linked list
clone.next=clone.next.next if clone.next!=None else clone.next
clone=clone.next
#Return the cloned linked list
return temporary_reference1
#Creating First node of the linked list
head = Node(10)
#Creating Second node of the linked list
head.next = Node(11)
#Creating Third node of the linked list
head.next.next = Node(12)
#Creating random reference of the First node to its own
head.random = head
#Printing the original Linked list
print("Original Linked list:")
#Transversing the original linked list
transverse(head)
#Printing the clone linked list
print("Clone Linked List")
#Calling function to create a clone of the linked list
clone=clone(head)
#Transversing the Cloned Linked list
transverse(clone)
Output
C++ Program
//Importing all the required libraries
#include
#include
#include<bits/stdc++.h>
using namespace std;
//Creating structure for the node of linked list
struct Node{
int data;//data to be stored to the node in the linked list
Node*random; //random Pointer to the node in the linked list
Node*next;//next reference to the node in the linked list
//Creating Constructor
Node(int data){
this->data=data; //Storing the data to the node
this->next=nullptr;
this->random=nullptr;
}
};
//Function to Transverse the Linked list
void transverse(Node *head){
//Checking if the Linked list is null or not
if(head==NULL){
return;
}
//Transverse the Linked List
while(head!=NULL){
//Checking if the random pointer is null or not
if(head->random!=NULL){
cout<data;
cout<<"->";
cout<random->data;
}
else{
cout<data;
cout<<"-> 0 ";
}
cout<<"\n"; head=head->next;
}
}
void clone(Node *head){
if(head==NULL){
return ;
}
//Creating a new reference of the head
Node *original_node=head;
//Creating temporary reference
Node *temporary_reference=NULL;
while(original_node!=NULL) {
//Inserting copy of node and insert to its adjacent position in the linked list
temporary_reference=original_node->next;
original_node->next=new Node(original_node->data);
original_node->next->next=temporary_reference;
//Update the node
original_node=temporary_reference;
}
//Initialize the head of the Linked list to the original_node
original_node=head;
while(original_node!=NULL) {
//Adjust the random pointer to the new created copy node in the original linked list
original_node->next->random=(original_node->random!=NULL)?original_node->random->next:NULL;
//Update the position of the original Linked list
original_node=original_node->next->next;
}
original_node=head;
//Creating cloning of the linked list
Node *clone=head->next;
Node *temporary_reference1=clone;
while(clone!=NULL) {
//Copy the all the nodes from the original linked list
clone->next=clone->next!=NULL?clone->next->next:clone->next;
clone=clone->next;
}
//Return the cloned linked list
transverse(temporary_reference1);
}
int main(){
//Creating Head of the linked list
Node *head =new Node(10);
//Creating Second node of the linked list
head->next=new Node(11);
//Creating third node of the linked list
head->next->next=new Node(12);
//Creating Random reference of the head node to its own node of the linked list.
head->random=head;
printf("Printing original Linked List\n");
transverse(head);
printf("Printing the cloned linked list\n");
clone(head);
return 0;
}
Output:
Complexity:
- Time complexity : O(n). The Time Complexity of this problem is O(n).
- Auxiliary Space :O(1). The Space Complexity of this problem is O(1).
Conclusion
Cloning a Linked list with the Random Pointer is one of the most frequently asked problems in most companies during technical interviews. In this article, we have discussed two approaches: one is a naive approach using map data structure and the second one is a tricky approach, and this is the most efficient approach to this problem.
We certainly hope that this article will help you understand this problem in greater detail, and you will now be able to solve it and any variation of it quite easily.
Happy Learning!
People are also reading:
Leave a Comment on this Post