Clone A Linked List With Next And Random Pointer In C++

In this article, you will learn about how to clone a linked list with next and Random Pointer in C++.

• ✅ Each node in a linked list of size N has two connections: one points to the node immediately following it, and the other can point to any other node in the list. This linked list must be duplicated in O(N) time.
• ✅ Keep in mind that the "arbit" pointer may randomly go to any node in the linked list, whereas the "next" pointer points to the node that follows in the linked list.
• ✅ The image below displays a linked list example:

To establish a connection between the new nodes and their corresponding nodes in the existing linked list, it is essential to construct a linked list that only contains the 'next' pointer. This linked list serves as a reference for linking any node from the new list to any other node as needed.

To implement the above concept, follow these steps:

• ✅ Duplicate every node (referred to as X) as another node (referred to as Y), and then establish a mapping between each new node and its original node, such that the mapping mp[X] = Y.
• ✅ Using only the 'next' pointer in each node, a linked list of duplicated nodes is generated.

During the previous cycles of traversing the linked list, repeat the following steps:

• ✅ Detect the unnecessary node connected to the main one. (For example, if X represents the current node, then mp[x] indicates the replica.)
• ✅ Adjust the pointer of the duplicate of the current->arbit node to refer to the duplicate of that node (thus, ensuring that mp[x]->arbicpp tutorials points to mp[X->arbit]).

The necessary linked list, which functions as a linked list, is generated through this process.

For clarification, refer to the figure below:

Illustration:

Consider the linked list depicted beneath:

• ✅ The articles on arbicpp are the highlighted hyperlinks.

Making a duplicate of Nodes and the nexcpp tutorialer:

• ✅ Create a single linked list of duplicate nodes at first, mapping the new nodes to the old ones using only the nexcpp tutorialers.
• ✅ Here, the mapping is displayed via the blue links.

Linking the arbicpp tutorialers:

As specified in the method, proceed to iterate through the existing array and update the arbicpp guide references. These arbicpp guides are represented by the green hyperlinks.

At first node:

At second node:

At Third node:

At fourth node:

At fifth node:

The final linked list is as shown below:

Program:

Let's consider an instance to illustrate the process of duplicating a linked list with both next and random pointers in the C++ programming language.

#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node* next;
Node* arbit;
Node(int x)
{
this->val = x;
this->next = NULL;
this->arbit = NULL;
}
};
Node* cloneLinkedList(Node* head)
{
unordered_map<Node*, Node*> mp;
Node *temp, *nhead;
temp = head;
nhead = new Node(temp->val);
mp[temp] = nhead;
while (temp->next != NULL) {
nhead->next = new Node(temp->next->val);
temp = temp->next;
nhead = nhead->next;
mp[temp] = nhead;
}
temp = head;
while (temp != NULL) {
mp[temp]->arbit = mp[temp->arbit];
temp = temp->next;
}
return mp[head];
}
void printList(Node* head)
{
cout << head->val << "("<< head->arbit->val << ")";
head = head->next;
while (head != NULL) {
cout << " -> " << head->val << "("<< head->arbit->val << ")";
head = head->next;
}
cout << endl;
}
int main()
{
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->arbit = head->next->next;
head->next->arbit = head;
head->next->next->arbit = head->next->next->next->next;
head->next->next->next->arbit = head->next->next;
head->next->next->next->next->arbit = head->next;
cout << "The original linked list:\n";
printList(head);
Node* sol = cloneLinkedList(head);
cout << "The cloned linked list:\n";
printList(sol);
return 0;
}

Output: