# Clone a Linked list with the Random Pointer

Posted in

Vinay Khatri
Last updated on September 21, 2024

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.

#### 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 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
//Checking if the Linked list is null or not
return ;
}
//Checking if the random pointer is null or not
}
else{
}

}
}
HashMap<Node,Node>H=new HashMap<Node,Node>();

}
//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);
}
}

public static void main(String args[]){
//Creating Second node of the linked list
//Creating third node of the linked list
//Creating fourth node of the linked list
//Creating Random reference of the head node to the second node of the linked list.
//Creating Random reference of third node to the second node of the linked list
//Creating a new line
System.out.println();

Transverse(clone);
}
}``````

#### 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
#Checking the base case
return None
#Checking the Random Reference in the node of the linked list
#If Random Reference Present in the node print

#Condition if node does not contains random pointer
else:

#Reference the next node in the linked list
#Function to make clone of the original linked list
#Creating temporary reference of the linked list
#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

#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

#Creating First node of the linked list
#Creating Second node of the linked list
#Creating Third node of the linked list
#Creating random reference of the First node to its own
#Calling function to create a clone of the linked list

transverse(clone)``````

#### 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
//Checking if the Linked list is null or not
return;
}
//Checking if the random pointer is null or not
cout<data;
cout<<"->";
cout<random->data;

}
else{
cout<data;
cout<<"-> 0 ";
}
}

}
return;
}

// Traverse the original list and make a copy in the map.
{
}

// Initialize original list again.

//Iterate the Map containing node and its reference
{
}

//Transverse the head of the map

}
int main(){
//Creating Second node of the linked list
//Creating third node of the linked list
//Creating Random reference of the head node to its own node of the linked list.
return 0;
}``````

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

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 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
//Checking if the Linked list is null or not
return ;
}
//Checking if the random pointer is null or not
}
else{
}

}
}
//Creating a new reference of the 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;
original_node=temporary_reference;

}

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;
}

//Creating cloning of the linked list
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  temporary_reference1;
}

public static void main(String args[]){
//Creating Second node of the linked list
//Creating third node of the linked list
//Creating fourth node of the linked list
//Creating Random reference of the head node to the second node of the linked list.
//Creating Random reference of third node to the second node of the linked list
//Creating a new line
System.out.println();

Transverse(clone);
}
}``````

#### 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
#Checking the base case
return None
#Checking the Random Reference in the node of the linked list
#If Random Reference Present in the node print

#Condition if node does not contains random pointer
else:

#Reference the next node in the linked list
#Function to make clone of the original linked list
#Creating temporary reference of the linked list
#//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
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
#Creating cloning of the linked list
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  temporary_reference1

#Creating First node of the linked list
#Creating Second node of the linked list
#Creating Third node of the linked list
#Creating random reference of the First node to its own
#Calling function to create a clone of the 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
//Checking if the Linked list is null or not
return;
}
//Checking if the random pointer is null or not
cout<data;
cout<<"->";
cout<random->data;

}
else{
cout<data;
cout<<"-> 0 ";
}
}

}
return ;
}
//Creating a new reference of the 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;

}

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;
}

//Creating cloning of the linked list

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;
}
transverse(temporary_reference1);

}
int main(){
//Creating Second node of the linked list
//Creating third node of the linked list
//Creating Random reference of the head node to its own node of the linked list.

return 0;

}``````

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