Q:

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

mahmoud2506
Save to bookmark
|
2022-05-08
|
  200 
0

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:

Clone a linked list

Output

Make a same copy of that linked list.

 

C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-08
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)

Data Structure programs using C and C++ (Linked List Programs)
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
C program to search an item in the linked list... >>
<< Delete N nodes after M nodes of a linked list usin...