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.
Table of Content
[Naive Approach] Using Hashing - O(n) Time and O(n) Space
The idea is to create a new node for each original node, store them in a hash table, then update the next and random pointers of the new nodes.
Try it on GfG Practice
- Create a hash table mp to map original nodes to new nodes.
- Traverse the original list and for each node curr, create a new node and store it in the hash table mp[curr] = new Node().
- Traverse the list again to update the next and random pointers of the new nodes: mp[curr]->next = mp[curr->next] and mp[curr]->random = mp[curr->random].
- Return mp[head] as the head of the cloned linked list.
#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;
}
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);
}
}
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)
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);
}
}
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)
[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.
- Traverse the list and insert a cloned node after each original node. For every node X, create X', place it as X -> X' -> next.
- Traverse again and update the random pointers of cloned nodes. X'->random = X->random->next (if random exists).
- Traverse the list again to separate the two lists. Restore original links and extract cloned links.
- Fix pointers: original->next = original->next->next, clone->next = clone->next->next.
- Return the head of the cloned list.
#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;
}
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);
}
}
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)
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);
}
}
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)