Q:

# Clone a linked list with next and random pointer using C++ program

Given a linked list, there are two node pointers one point to the next node of the linked list and another is the random pointer which points to any random node of that linked list. Your task is to make a clone a linked list of that linked list.

Example:

Input:

Output

Make a same copy of that linked list.

### All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

Node structure for random pointer:

```    Node temp
{
Int data;
Node* next;
Node* random=NULL;
}
```

To solve that problem we follow this algorithm:

1. First, we copy the next pointers and make a linked list.
2. In the second iteration, we copy the random pointers of that linked list.

Using this algorithm the time complexity is O(n).

C++ implementation:

``````#include <bits/stdc++.h>
using namespace std;

struct node {
int data;
node* next;
node* random;
};

//Create a new node
struct node* create_node(int x)
{
struct node* temp = new node;
temp->data = x;
temp->next = NULL;
temp->random = NULL;
return temp;
}

void push_random(node* head, int x, int y)
{
struct node* temp1 = head;
while (temp1) {
if (temp1->data == x) {
break;
}
temp1 = temp1->next;
}
struct node* temp2 = head;
while (temp2) {
if (temp2->data == y) {
break;
}
temp2 = temp2->next;
}
temp1->random = temp2;
}

//Enter the node into the linked list
void push(node** head, int x)
{
struct node* store = create_node(x);
if (*head == NULL) {
*head = store;
return;
}
struct node* temp = *head;
while (temp->next) {
temp = temp->next;
}
temp->next = store;
}

//Reverse the linked list
struct node* copy(node* head)
{
struct node* temp = head;
struct node* store = create_node(0);
struct node* curr = store;
while (temp) {
curr->next = create_node(temp->data);
temp = temp->next;
curr = curr->next;
}
temp = head;
curr = store;
while (temp) {
curr->random = temp->random;
curr = curr->next;
temp = temp->next;
}
store = store->next;
return store;
}

//Print the list
void print(node* head)
{
struct node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
}

int main()
{
struct node* l = NULL;
push(&l, 1);
push(&l, 2);
push(&l, 3);
push(&l, 4);
push(&l, 5);
push(&l, 6);
srand(time(0));
for (int i = 1; i <= 6; i++) {
int r = (rand() % 6) + 1;
push_random(l, i, r);
}
cout << "Original list" << endl;
print(l);
struct node* c = copy(l);
cout << "\nCopy list" << endl;
print(c);

return 0;
}``````

Output

```Original list
1 2 3 4 5 6
Copy list
1 2 3 4 5 6
```

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)