Each node in a linked list of size N contains two links: a random pointer to any random node in the list and a next pointer to the next node. Making a copy of this linked list is the work at hand.
Table of Content
- [Naive Approach – 1] Using Hashing – O(2n) Time and O(2n) Space
- [Naive Approach – 2] Using Hashing and Recursion- O(n) Time and O(3n) Space
- [Expected Approach] By Inserting Nodes In-place – O(3n) Time and O(1) Space
How to use a random pointer and next to clone a linked list:
To store the new nodes that correspond to their original nodes, create a hash table with the value mp.
For each node in the original linked list, say curr,
mp[curr] = new Node() creates a new node that corresponds to curr and pushes it into a hash table.
To update the next and random pointer of every new node, iterate through the original linked list once more: mp[curr]->next = mp[curr->next] and mp[curr]->random = mp[curr->random].
Return the cloned linked list’s head, mp[head].
The application of the aforementioned strategy is seen below:
C++14
// C++ code to Clone a linked list with next and random
// pointer using Hashing
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
Node* random;
Node(int x) {
data = x;
next = random = NULL;
}
};
// Function to clone the linked list
Node* cloneLinkedList(Node* head) {
// Map to store new nodes corresponding to
// their original nodes
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) {
// Update the next pointer of new node
mp[curr]->next = mp[curr->next];
// Update the random pointer of new node
mp[curr]->random = mp[curr->random];
curr = curr->next;
}
// Return the head of the clone
return mp[head];
}
// Function to print the linked list
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);
// Function call
Node* clonedList = cloneLinkedList(head);
cout << "Cloned linked list:\n";
printList(clonedList);
return 0;
}
Java
// Java code to Clone a linked list with next and random
// pointer using Hashing
import java.util.HashMap;
import java.util.Map;
// Define the Node class
class Node {
int data;
Node next;
Node random;
Node(int x) {
data = x;
next = null;
random = null;
}
}
class GfG {
// Function to clone the linked list
static Node cloneLinkedList(Node head) {
// Hash Map to store new nodes corresponding
// to their original nodes
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) {
// Update the next pointer of new node
Node newNode = mp.get(curr);
newNode.next = mp.get(curr.next);
// Update the random pointer of new node
newNode.random = mp.get(curr.random);
curr = curr.next;
}
// Return the head of the clone
return mp.get(head);
}
// Function to print the linked list
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);
// Function call
Node clonedList = cloneLinkedList(head);
System.out.println("Cloned linked list:");
printList(clonedList);
}
}Python
# Python code to Clone a linked list with next and random
# pointer using Hashing
class Node:
def __init__(self, x):
self.data = x
self.next = None
self.random = None
# Function to clone the linked list
def clone_linked_list(head):
# Dictionary to store new nodes corresponding
# to their original nodes
mp = {}
curr = head
# Traverse original linked list to store new nodes
# corresponding to original linked list
while curr is not None:
mp[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:
new_node = mp[curr]
# Update the next pointer of new node
new_node.next = mp.get(curr.next)
# Update the random pointer of new node
new_node.random = mp.get(curr.random)
curr = curr.next
# Return the head of the clone
return mp.get(head)
def print_list(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:")
print_list(head)
# Function call
cloned_list = clone_linked_list(head)
print("Cloned linked list:")
print_list(cloned_list)JS
// JavaScript code to Clone a linked list with next
// and random pointer using Hashing
class Node {
constructor(data) {
this.data = data;
this.next = null;
this.random = null;
}
}
// Function to clone the linked list
function cloneLinkedList(head) {
// Map to store new nodes corresponding to
// their original nodes
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 the head of the clone
return mp.get(head) || null;
}
// Function to print the linked list
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
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);
// Function call
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)
Time Complexity: O(2n), as we are traversing the linked list twice.
Auxiliary Space: O(2n), extra O(n) space as we are using a hash table to store the new nodes.