Clon de una lista enlazada con el puntero al lado y al azar mediante el programa C ++

En este artículo, vamos a aprender cómo clonar una lista enlazada con el siguiente puntero al azar? Este artículo contiene planteamiento del problema, la explicación, algoritmo, C ++ aplicación y la salida.

Planteamiento del problema:

Dada una lista enlazada, hay dos punteros a nodos de un punto al siguiente nodo de la lista enlazada y otro es el puntero al azar que apunta a cualquier nodo al azar de esa lista enlazada. Su tarea es hacer un clon de una lista enlazada de esa lista enlazada .

Ejemplo:

de entrada:

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

salida

Hacer una misma copia de esa lista enlazada.

Algoritmo: puntero al azar

Nodo estructura class:

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

Para resolver ese problema se sigue este algoritmo:

  1. En primer lugar, copiamos los siguientes puntos y construir una lista enlazada.
  2. En la segunda iteración, copiamos los punteros aleatorios de que la lista enlazada.

El uso de este algoritmo de la complejidad de tiempo es O (n) .

implementación en C ++:

#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;
}

salida

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


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *