Open In App

Clone a Linked List with Random Pointer

Last Updated : 02 Sep, 2025
Suggest changes
Share
Like Article
Like
Report

Given a head of linked list where each node has two links: next pointer pointing to the next node and random pointer to any random node in the list. Create a clone of this linked list.

file

Table of Content

[Naive Approach - 1] Using Hashing - O(n) Time and O(n) Space

The idea is to create a new node corresponding to each node in the original linked list and store the new nodes in a hash table. Now, again traverse the original linked list and update the next and random pointers of new nodes corresponding to every original node.

Illustration:

Algorithm:

  • Create a hash table, say mp to store the new nodes corresponding to their original nodes.
  • Traverse the original linked list and for every node, say curr,
    => Create a new node corresponding to curr and push them into a hash table, mp[curr] = new Node().
  • Again traverse the original linked list to update the next and random pointer of each new node, mp[curr]->next = mp[curr->next] and mp[curr]->random = mp[curr->random].
  • Return mp[head] as the head of the cloned linked list.
C++ 
#include <iostream> #include <unordered_map> using namespace std; class Node { public:  int data;  Node* next;  Node* random;    Node(int x) {  data = x;  next = random = NULL;  } }; Node* cloneLinkedList(Node* head) {    unordered_map<Node*, Node*> mp;  Node *curr = head;    // Traverse original linked list to store new   // nodes corresponding to original linked list  while (curr != NULL) {  mp[curr] = new Node(curr->data);  curr = curr->next;  }    curr = head;    // Loop to update the next and random pointers   // of new nodes   while (curr != NULL) {    mp[curr]->next = mp[curr->next];    mp[curr]->random = mp[curr->random];    curr = curr->next;  }  return mp[head]; } void printList(Node* head) {  while (head != NULL) {  cout << head->data << "(";  if(head->random)  cout << head->random->data << ")";  else   cout << "null" << ")";    if(head->next != NULL)  cout << " -> ";  head = head->next;  }  cout << endl; } int main() {    // Creating a linked list with random pointer  Node* head = new Node(1);  head->next = new Node(2);  head->next->next = new Node(3);  head->next->next->next = new Node(4);  head->next->next->next->next = new Node(5);  head->random = head->next->next;  head->next->random = head;  head->next->next->random = head->next->next->next->next;  head->next->next->next->random = head->next->next;  head->next->next->next->next->random = head->next;    // Print the original list  cout << "Original linked list:\n";  printList(head);    Node* clonedList = cloneLinkedList(head);    cout << "Cloned linked list:\n";  printList(clonedList);    return 0; }
Java 
import java.util.HashMap; import java.util.Map; class Node {  int data;  Node next;  Node random;    Node(int x) {  data = x;  next = null;  random = null;  } } class GfG {  static Node cloneLinkedList(Node head) {    Map<Node, Node> mp = new HashMap<>();  Node curr = head;    // Traverse original linked list to store new nodes   // corresponding to original linked list  while (curr != null) {  mp.put(curr, new Node(curr.data));  curr = curr.next;  }    curr = head;    // Loop to update the next and random pointers  // of new nodes   while (curr != null) {    Node newNode = mp.get(curr);  newNode.next = mp.get(curr.next);    newNode.random = mp.get(curr.random);    curr = curr.next;  }    return mp.get(head);  }  static void printList(Node head) {  while (head != null) {  System.out.print(head.data + "(");  if (head.random != null)  System.out.print(head.random.data + ")");  else   System.out.print("null" + ")");    if (head.next != null)  System.out.print(" -> ");  head = head.next;  }  System.out.println();  }  public static void main(String[] args) {    // Creating a linked list with random pointer  Node head = new Node(1);  head.next = new Node(2);  head.next.next = new Node(3);  head.next.next.next = new Node(4);  head.next.next.next.next = new Node(5);  head.random = head.next.next;  head.next.random = head;  head.next.next.random = head.next.next.next.next;  head.next.next.next.random = head.next.next;  head.next.next.next.next.random = head.next;    // Print the original list  System.out.println("Original linked list:");  printList(head);    Node clonedList = cloneLinkedList(head);    System.out.println("Cloned linked list:");  printList(clonedList);  } }
Python 
class Node: def __init__(self, x): self.data = x self.next = None self.random = None def cloneLinkedList(head): nodeMap = {} curr = head # Traverse original linked list to store new nodes  # corresponding to original linked list while curr is not None: nodeMap[curr] = Node(curr.data) curr = curr.next curr = head # Loop to update the next and random pointers # of new nodes while curr is not None: newNode = nodeMap[curr] newNode.next = nodeMap.get(curr.next) newNode.random = nodeMap.get(curr.random) curr = curr.next return nodeMap.get(head) def printList(head): curr = head while curr is not None: print(f'{curr.data}(', end='') if curr.random: print(f'{curr.random.data})', end='') else: print('null)', end='') if curr.next is not None: print(' -> ', end='') curr = curr.next print() if __name__ == "__main__": # Creating a linked list with random pointer head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) head.random = head.next.next head.next.random = head head.next.next.random = head.next.next.next.next head.next.next.next.random = head.next.next head.next.next.next.next.random = head.next # Print the original list print("Original linked list:") printList(head) clonedList = cloneLinkedList(head) print("Cloned linked list:") printList(clonedList)
C# 
using System; using System.Collections.Generic; class Node {  public int Data;  public Node Next;  public Node Random;  public Node(int x) {  Data = x;  Next = null;  Random = null;  } } class GfG {    static Node cloneLinkedList(Node head) {    Dictionary<Node, Node> mp = new Dictionary<Node, Node>();  Node curr = head;  // Traverse original linked list to store new nodes  // corresponding to original linked list  while (curr != null) {  mp[curr] = new Node(curr.Data);  curr = curr.Next;  }  curr = head;  // Loop to update the next and random pointers of new nodes  while (curr != null) {  Node newNode = mp[curr];  if(curr.Next != null)  newNode.Next = mp[curr.Next];  newNode.Random = mp[curr.Random];  curr = curr.Next;  }  return mp[head];  }  static void PrintList(Node head) {  while (head != null) {  Console.Write(head.Data + "(");  if (head.Random != null)  Console.Write(head.Random.Data);  else  Console.Write("null");  Console.Write(")");  if (head.Next != null)  Console.Write(" -> ");  head = head.Next;  }  Console.WriteLine();  }  static void Main(string[] args) {    // Creating a linked list with random pointer  Node head = new Node(1);  head.Next = new Node(2);  head.Next.Next = new Node(3);  head.Next.Next.Next = new Node(4);  head.Next.Next.Next.Next = new Node(5);  head.Random = head.Next.Next;  head.Next.Random = head;  head.Next.Next.Random = head.Next.Next.Next.Next;  head.Next.Next.Next.Random = head.Next.Next;  head.Next.Next.Next.Next.Random = head.Next;  // Print the original list  Console.WriteLine("Original linked list:");  PrintList(head);  Node clonedList = cloneLinkedList(head);  Console.WriteLine("Cloned linked list:");  PrintList(clonedList);  } }
JavaScript 
class Node {  constructor(data) {  this.data = data;  this.next = null;  this.random = null;  } } function cloneLinkedList(head) {    const mp = new Map();  let curr = head;  // Traverse original linked list to store new nodes  // corresponding to original linked list  while (curr !== null) {  mp.set(curr, new Node(curr.data));  curr = curr.next;  }    curr = head;    // Loop to update the next and random pointers  // of new nodes  while (curr !== null) {  const newNode = mp.get(curr);  newNode.next = mp.get(curr.next) || null;  newNode.random = mp.get(curr.random) || null;  curr = curr.next;  }    return mp.get(head) || null; } function printList(head) {  let result = "";  while (head !== null) {  result += head.data + "(";  result += head.random ? head.random.data : "null";  result += ")";  if (head.next !== null) {  result += " -> ";  }  head = head.next;  }  console.log(result); } // Driver Code // Creating a linked list with random pointer const head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.random = head.next.next; head.next.random = head; head.next.next.random = head.next.next.next.next; head.next.next.next.random = head.next.next; head.next.next.next.next.random = head.next; // Print the original list console.log("Original linked list:"); printList(head); const clonedList = cloneLinkedList(head); console.log("Cloned linked list:"); printList(clonedList);

Output
Original linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2) Cloned linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2)

[Naive Approach - 2] Using Hashing and Recursion- O(n) Time and O(n) Space

The idea is to create a new node corresponding to each node in the original linked list and store the new nodes in a hash table. While traversing the original linked list we also use recursion to update the next and random pointers of new nodes corresponding to every original node.

For a more detailed solution and code checkout, this article Clone a linked list with next and random pointer using Recursion

[Expected Approach] By Inserting Nodes In-place - O(n) Time and O(1) Space

The idea is to create duplicate of a node and instead of storing in a separate hash table, we can insert it in between the original node and the next node. Now, we will have new nodes at alternate positions.

Now for a node X its duplicate will be X->next and the random pointer of the duplicate should point to X->random->next (as that is the duplicate of X->random). So, iterate over the entire linked list to update the random pointer of all the cloned nodes and then iterate again to separate the original linked list and the cloned linked list.

Illustration:

Step By Step Implementations:

  • Create the copy of node 1 and insert it between node 1 and node 2 in the original Linked List, create the copy of node 2 and insert it between 2nd and 3rd node and so on. Add the copy of n after the nth node 
  • Connect the clone node by updating the random pointers.
  • Separate the cloned linked list from the original list by updating the next pointers. 
C++ 
#include <iostream> using namespace std; class Node { public:  int data;  Node *next, *random;  Node(int x) {  data = x;  next = random = NULL;  } }; Node* cloneLinkedList(Node* head) {  if (head == NULL) {  return NULL;  }    // Create new nodes and insert them next to   // the original nodes  Node* curr = head;  while (curr != NULL) {  Node* newNode = new Node(curr->data);  newNode->next = curr->next;  curr->next = newNode;  curr = newNode->next;  }    // Set the random pointers of the new nodes  curr = head;  while (curr != NULL) {  if (curr->random != NULL)  curr->next->random = curr->random->next;  curr = curr->next->next;  }    // Separate the new nodes from the original nodes  curr = head;  Node* clonedHead = head->next;  Node* clone = clonedHead;  while (clone->next != NULL) {    // Update the next nodes of original node   // and cloned node  curr->next = curr->next->next;  clone->next = clone->next->next;    // Move pointers of original as well as   // cloned linked list to their next nodes  curr = curr->next;  clone = clone->next;  }  curr->next = NULL;  clone->next = NULL;    return clonedHead; } void printList(Node* head) {  while (head != NULL) {  cout << head->data << "(";  if(head->random)  cout << head->random->data << ")";  else   cout << "null" << ")";    if(head->next != NULL)  cout << " -> ";  head = head->next;  }  cout << endl; } int main() {    // Creating a linked list with random pointer  Node* head = new Node(1);  head->next = new Node(2);  head->next->next = new Node(3);  head->next->next->next = new Node(4);  head->next->next->next->next = new Node(5);  head->random = head->next->next;  head->next->random = head;  head->next->next->random = head->next->next->next->next;  head->next->next->next->random = head->next->next;  head->next->next->next->next->random = head->next;    // Print the original list  cout << "Original linked list:\n";  printList(head);    Node* clonedList = cloneLinkedList(head);    cout << "Cloned linked list:\n";  printList(clonedList);    return 0; }
Java 
class Node {  int data;  Node next, random;    Node(int x) {  data = x;  next = random = null;  } } class GfG {    static Node cloneLinkedList(Node head) {  if (head == null) {  return null;  }    // Create new nodes and insert them  // next to the original nodes  Node curr = head;  while (curr != null) {  Node newNode = new Node(curr.data);  newNode.next = curr.next;  curr.next = newNode;  curr = newNode.next;  }    // Set the random pointers of the new nodes  curr = head;  while (curr != null) {  if (curr.random != null) {  curr.next.random = curr.random.next;  }  curr = curr.next.next;  }    // Separate the new nodes from the original nodes  curr = head;  Node clonedHead = head.next;  Node clone = clonedHead;  while (clone.next != null) {    // Update the next nodes of original node  // and cloned node  curr.next = curr.next.next;  clone.next = clone.next.next;    // Move pointers of original and cloned  // linked list to their next nodes  curr = curr.next;  clone = clone.next;  }  curr.next = null;  clone.next = null;    return clonedHead;  }    static void printList(Node head) {  while (head != null) {  System.out.print(head.data + "(");  if (head.random != null) {  System.out.print(head.random.data);  } else {  System.out.print("null");  }  System.out.print(")");    if (head.next != null) {  System.out.print(" -> ");  }  head = head.next;  }  System.out.println();  }    public static void main(String[] args) {    // Creating a linked list with random pointer  Node head = new Node(1);  head.next = new Node(2);  head.next.next = new Node(3);  head.next.next.next = new Node(4);  head.next.next.next.next = new Node(5);  head.random = head.next.next;  head.next.random = head;  head.next.next.random = head.next.next.next.next;  head.next.next.next.random = head.next.next;  head.next.next.next.next.random = head.next;    // Print the original list  System.out.println("Original linked list:");  printList(head);    Node clonedList = cloneLinkedList(head);    System.out.println("Cloned linked list:");  printList(clonedList);  } }
Python 
class Node: def __init__(self, x): self.data = x self.next = None self.random = None def cloneLinkedList(head): if head is None: return None # Create new nodes and insert them next to  # the original nodes curr = head while curr is not None: newNode = Node(curr.data) newNode.next = curr.next curr.next = newNode curr = newNode.next # Set the random pointers of the new nodes curr = head while curr is not None: if curr.random is not None: curr.next.random = curr.random.next curr = curr.next.next # Separate the new nodes from the original nodes curr = head clonedHead = head.next clone = clonedHead while clone.next is not None: # Update the next nodes of original node  # and cloned node curr.next = curr.next.next clone.next = clone.next.next # Move pointers of original as well as  # cloned linked list to their next nodes curr = curr.next clone = clone.next curr.next = None clone.next = None return clonedHead def printList(head): while head is not None: print(f"{head.data}(", end="") if head.random: print(f"{head.random.data})", end="") else: print("null)", end="") if head.next is not None: print(" -> ", end="") head = head.next print() if __name__ == "__main__": # Creating a linked list with random pointer head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) head.random = head.next.next head.next.random = head head.next.next.random = head.next.next.next.next head.next.next.next.random = head.next.next head.next.next.next.next.random = head.next # Print the original list print("Original linked list:") printList(head) clonedList = cloneLinkedList(head) print("Cloned linked list:") printList(clonedList)
C# 
using System; using System.Collections.Generic; class Node {  public int Data;  public Node Next, Random;  public Node(int x) {  Data = x;  Next = Random = null;  } } class GfG {  static Node cloneLinkedList(Node head) {  if (head == null)  return null;  // Create new nodes and insert them next to   // the original nodes  Node curr = head;  while (curr != null) {  Node newNode = new Node(curr.Data);  newNode.Next = curr.Next;  curr.Next = newNode;  curr = newNode.Next;  }  // Set the random pointers of the new nodes  curr = head;  while (curr != null) {  if (curr.Random != null)  curr.Next.Random = curr.Random.Next;  curr = curr.Next.Next;  }  // Separate the new nodes from the original nodes  curr = head;  Node clonedHead = head.Next;  Node clone = clonedHead;  while (clone.Next != null) {    // Update the next nodes of original node   // and cloned node  curr.Next = curr.Next.Next;  clone.Next = clone.Next.Next;  // Move pointers of original as well as   // cloned linked list to their next nodes  curr = curr.Next;  clone = clone.Next;  }  curr.Next = null;  clone.Next = null;  return clonedHead;  }  static void printList(Node head) {  while (head != null) {  Console.Write(head.Data + "(");  if (head.Random != null)  Console.Write(head.Random.Data + ")");  else  Console.Write("null)");    if (head.Next != null)  Console.Write(" -> ");  head = head.Next;  }  Console.WriteLine();  }  public static void Main() {    // Creating a linked list with random pointer  Node head = new Node(1);  head.Next = new Node(2);  head.Next.Next = new Node(3);  head.Next.Next.Next = new Node(4);  head.Next.Next.Next.Next = new Node(5);  head.Random = head.Next.Next;  head.Next.Random = head;  head.Next.Next.Random = head.Next.Next.Next.Next;  head.Next.Next.Next.Random = head.Next.Next;  head.Next.Next.Next.Next.Random = head.Next;  // Print the original list  Console.WriteLine("Original linked list:");  printList(head);  Node clonedList = cloneLinkedList(head);  Console.WriteLine("Cloned linked list:");  printList(clonedList);  } }
JavaScript 
class Node {  constructor(data) {  this.data = data;  this.next = null;  this.random = null;  } } function cloneLinkedList(head) {  if (head === null) {  return null;  }  // Create new nodes and insert them next to the   // original nodes  let curr = head;  while (curr !== null) {  let newNode = new Node(curr.data);  newNode.next = curr.next;  curr.next = newNode;  curr = newNode.next;  }  // Set the random pointers of the new nodes  curr = head;  while (curr !== null) {  if (curr.random !== null) {  curr.next.random = curr.random.next;  }  curr = curr.next.next;  }  // Separate the new nodes from the original nodes  curr = head;  let clonedHead = head.next;  let clone = clonedHead;  while (clone.next !== null) {    // Update the next nodes of original node and cloned node  curr.next = curr.next.next;  clone.next = clone.next.next;  // Move pointers of original as well as cloned  // linked list to their next nodes  curr = curr.next;  clone = clone.next;  }  curr.next = null;  clone.next = null;  return clonedHead; } function printList(head) {  let result = "";  while (head !== null) {  result += head.data + "(";  result += head.random ? head.random.data : "null";  result += ")";  if (head.next !== null) {  result += " -> ";  }  head = head.next;  }  console.log(result); } // Creating a linked list with random pointer let head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.random = head.next.next; head.next.random = head; head.next.next.random = head.next.next.next.next; head.next.next.next.random = head.next.next; head.next.next.next.next.random = head.next; // Print the original list console.log("Original linked list:"); printList(head); let clonedList = cloneLinkedList(head); console.log("Cloned linked list:"); printList(clonedList);

Output
Original linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2) Cloned linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2)

K
kartik

Explore

Article Tags :
Lightbox