How to use a random pointer and next to clone a linked list:
- To store each original node to its matching cloned node, create a hash table with the value mp.
- Function for Recursive Cloning:
- Return nullptr if the current node (head) is nullptr.
- Give back the cloned node from the hash table if the node is already there (mp).
- With the same data as the current node, create a new node (clonedNode) and store it in the hash table (mp[head] = clonedNode).
- Clone the current node’s next and random pointers recursively:
- Call the recursive procedure on head->next to update the clonedNode’s next pointer.
- Call the recursive procedure on head->random to update the clonedNode’s random pointer.
- Return the Cloned List Head after cloning.
C++
// C++ code to Clone a linked list with next
// and random pointer using Hashing and Recursion
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *next;
Node *random;
Node(int x) {
data = x;
next = random = NULL;
}
};
// Helper function to clone the list
Node *cloneHelper(Node*head, unordered_map<Node*, Node*> &mp) {
if (head == nullptr) {
return nullptr;
}
// If the node is already cloned, return the cloned node
if (mp.find(head) != mp.end()) {
return mp[head];
}
// Create a new node with the same data
Node *clonedNode = new Node(head->data);
mp[head] = clonedNode;
// Recursively clone the next and random pointers
clonedNode->next = cloneHelper(head->next, mp);
clonedNode->random = cloneHelper(head->random, mp);
return clonedNode;
}
// Function to clone the linked list
Node *cloneLinkedList(Node *head) {
unordered_map<Node *, Node *> mp;
return cloneHelper(head, mp);
}
void printList(Node *head) {
while (head != nullptr) {
cout << head->data << "(";
if (head->random)
cout << head->random->data << ")";
else
cout << "null"
<< ")";
if (head->next != nullptr)
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;
Node *clonedList = cloneLinkedList(head);
printList(clonedList);
return 0;
}
Java
// Java code to Clone a linked list with next
// and random pointer using Hashing and Recursion
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 {
// Helper function to recursively clone nodes
static Node cloneHelper(Node node,Map<Node, Node> mp) {
if (node == null) {
return null;
}
// If the node is already cloned,
// return the cloned
// node
if (mp.containsKey(node)) {
return mp.get(node);
}
// Create a new node with the same data
Node newNode = new Node(node.data);
mp.put(node,newNode);
// Recursively clone the next and random pointers
newNode.next = cloneHelper(node.next, mp);
newNode.random = cloneHelper(node.random, mp);
return newNode;
}
// Function to clone the linked list
static Node cloneLinkedList(Node head) {
Map<Node, Node> mp = new HashMap<>();
return cloneHelper(head, mp);
}
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;
Node clonedList = cloneLinkedList(head);
printList(clonedList);
}
}
Python
# Python code to Clone a linked list with next
# and random pointer using Hashing and Recursion
class Node:
def __init__(self, x):
self.data = x
self.next = None
self.random = None
def clone_linked_list(head):
# Helper function to recursively clone nodes
def clone_helper(node, mp):
if node is None:
return None
if node in mp:
return mp[node]
# Create a new node
new_node = Node(node.data)
mp[node] = new_node
# Recursively clone the next and
# random pointers
new_node.next = clone_helper(node.next, mp)
new_node.random = clone_helper(node.random, mp)
return new_node
# Map to store original nodes
# to cloned nodes
mp = {}
return clone_helper(head, mp)
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
cloned_list = clone_linked_list(head)
print_list(cloned_list)
C#
// C# code to Clone a linked list with next
// and random pointer using Hashing and Recursion
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 {
// Function to clone the linked list
static Node CloneLinkedList(Node head) {
// Dictionary to store the mapping of original nodes
// to new nodes
Dictionary<Node, Node> mp =
new Dictionary<Node, Node>();
return CloneHelper(head, mp);
}
// Recursive helper function to clone the linked list
static Node CloneHelper(Node node, Dictionary<Node, Node> mp) {
// Base case: if the node is null, return null
if (node == null) {
return null;
}
// If the node has already been cloned, return the
// cloned node
if (mp.ContainsKey(node)) {
return mp[node];
}
// Create a new node for the current node
Node newNode = new Node(node.Data);
mp[node] = newNode;
// Recursively clone the next and random pointers
newNode.next = CloneHelper(node.next, mp);
newNode.random = CloneHelper(node.random, mp);
return newNode;
}
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;
Node clonedList = CloneLinkedList(head);
PrintList(clonedList);
}
}
JS
// Javascript code to Clone a linked list with next
// and random pointer using Hashing and Recursion
class Node {
constructor(data) {
this.data = data;
this.next = null;
this.random = null;
}
}
// Recursive function to clone the linked list
function cloneLinkedList(head) {
const mp = new Map();
// Recursive helper function
function cloneHelper(node) {
if (node === null) {
return null;
}
// If the node is already cloned,
// return the cloned
// node
if (mp.has(node)) {
return mp.get(node);
}
// Create a new node for the current node
const newNode = new Node(node.data);
mp.set(node, newNode);
// Recursively clone the next and random pointers
newNode.next = cloneHelper(node.next);
newNode.random = cloneHelper(node.random);
return newNode;
}
// Start the cloning process
return cloneHelper(head);
}
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;
const clonedList = cloneLinkedList(head);
printList(clonedList);
Output
1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2)
- Time complexity :Â O(n)Â , where n is the number of nodes in linked list.
- Auxiliary space :Â O(3n) , extra O(n) space as we are using a hash table to store the new nodes as well for recursion stack space.