Clone a Linked List with Next and Random Pointer in C++
In C++, cloning a linked list with a "next" and a "random" reference is a typical data structure and algorithmic issue. There are other names for this type of linked list, including "arbitrary pointer linked list" and "random pointer linked list". It serves as an example to assess your knowledge of linked lists and pointers, but it's not a typical C++ data structure.
Every node in this type of linked list possesses two pointers: one that leads to the node after it in the list, and the other that points to any random node in the list. In order to clone a linked list of this type, one must first create a new linked list that has the exact same structure and contents as the original list, making sure that the random pointers in the new list refer to the appropriate nodes.
Methods:
Node Class: For each entry in the linked list, a Node class needs to be defined. Three qualities are usually present in this class:
- Data: The information kept in the node.
- List: A reference to the node in the list that comes after it.
- Random: A reference to an arbitrary list node.
The primary way for cloning a linked list is the cloneRandomLinkedList function. Two passes exist:
First Pass: Copy nodes and associate them with their original nodes.
During the first run, you go over the original linked list, clone each original node, and save the mapping in a hash map between the original and cloned nodes. In the second run, it is done to make sure you can set the next and random pointers for the cloned nodes correctly.
Second pass: Update the random and next pointers for the cloned nodes in the second round. In the second run, you use the mapping kept in the hash map to iterate through the original linked list once more and change the next and random pointers for each cloned node.
Map Hashing: An original node's matching cloned node is mapped using a std::unordered_map. In the original and cloned linked lists, this map assists you in determining the proper relationships between nodes. The cloned node in matching relation to the key is the value.
Main function: The cloneRandomLinkedList method is called to build a cloned list, and you may optionally print both the original and cloned lists to confirm that the cloning procedure was successful. The main function creates an example linked list using random pointers.
Example:
Three nodes make up the initial linked list: Node 1 (data = "1," Node 2 (data = "2," and Node 3 (data = "3"). The "next" pointers (1 -> 2 -> 3) connect these nodes in a sequential manner. We also set "random" pointers just to add some intrigue to things. The "random" pointer on Node 1 points to Node 3, so establishing a connection from "1" to "3", and the "random" pointer on Node 2 points back to Node 1, establishing a link from "2" to "1". Using both "next" and "random" points to clone this linked list can present difficulties. We accomplish this by utilizing a hash map to map the original nodes to the cloned nodes. We do two passes through the original list: first, we clone the nodes and map them; second, we use the mappings to update the cloned nodes' "next" and "random" pointers. We can confirm that this process was successful by printing both lists and examining the data, "next", and "random" pointers. The output is a cloned linked list that replicates the structure and relationships of the original list.
Input:
head = [[1,3],[2,0],[3,null],[4,1]]
Output:
head = [[1,3],[2,0],[3,null],[4,1]]
C++ Code:
Let's take an example to demonstrate how we can clone a linked list with next and random pointers:
#include <iostream>
#include <unordered_map>
using namespace std;
class Node {
public:
int data;
Node* next;
Node* random;
Node(int val) : data(val), next(nullptr), random(nullptr) {}
};
Node* cloneRandomLinkedList(Node* head) {
unordered_map<Node*, Node*> nodeMap;
Node* original = head;
Node* cloned = nullptr;
while (original != nullptr) {
cloned = new Node(original->data);
nodeMap[original] = cloned;
original = original->next;
}
original = head;
while (original != nullptr) {
cloned = nodeMap[original];
cloned->next = nodeMap[original->next];
cloned->random = nodeMap[original->random];
original = original->next;
}
return nodeMap[head];
}
void printLinkedList(Node* head) {
Node* current = head;
while (current != nullptr) {
cout << "Data: " << current->data;
if (current->next) {
cout << ", Next: " << current->next->data;
}
if (current->random) {
cout << ", Random: " << current->random->data;
}
cout << endl;
current = current->next;
}
}
int main() {
Node* originalList = new Node(12);
originalList->next = new Node(24);
originalList->next->next = new Node(36);
originalList->random = originalList->next->next;
originalList->next->random = originalList;
Node* clonedList = cloneRandomLinkedList(originalList);
cout << "Original List:" << endl;
printLinkedList(originalList);
cout << "Cloned List:" << endl;
printLinkedList(clonedList);
return 0;
}
Output:
Original List:
Data: 12, Next: 24, Random: 36
Data: 24, Next: 36, Random: 12
Data: 36
Cloned List:
Data: 12, Next: 24, Random: 36
Data: 24, Next: 36, Random: 12
Data: 36
Conclusion:
Data structures and algorithms require the difficult but necessary task of cloning a linked list with both "next" and "random" points. Each node not only points to the next node but also to a random node inside the list. Therefore, managing the node associations carefully is necessary. We establish a mapping between the original nodes and the cloned nodes that correspond to them using a hash map to solve this problem. We can easily generate the cloned nodes using this mapping and then, in a second pass, change the "next" and "random" points accordingly. As a result, a cloned linked list that precisely matches the original list's relationships and structure is produced. This problem serves as an excellent illustration of the value of manipulating data structures and demonstrates the way an application's use of extra data structures, such as hash maps, can simplify challenging programming positions.