Ya hemos discutido 2 formas diferentes de clonar una lista enlazada. En esta publicación, se analiza otro método simple para clonar una lista vinculada.
La idea es usar Hashing. A continuación se muestra el algoritmo.
- Recorra la lista enlazada original y haga una copia en términos de datos.
- Cree un mapa hash del par de valores clave con el Node de lista enlazada original y el Node de lista enlazada copiado.
- Recorra la lista enlazada original nuevamente y, utilizando el mapa hash, ajuste la referencia siguiente y aleatoria de los Nodes de la lista enlazada clonados.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to clone a linked list
// with random pointers
#include<bits/stdc++.h>
using namespace std;
// Linked List Node
class Node
{
public:
// Node data
int data;
// Next and random reference
Node *next, *random;
Node(int data)
{
this->data = data;
this->next =
this->random = NULL;
}
};
// Linked list class
class LinkedList
{
public:
// Linked list head reference
Node *head;
LinkedList(Node *head)
{
this->head = head;
}
// Push method to put data always at
// the head in the linked list.
void push(int data)
{
Node *node = new Node(data);
node->next = head;
head = node;
}
// Method to print the list.
void print()
{
Node *temp = head;
while (temp != NULL)
{
Node *random = temp->random;
int randomData = ((random != NULL) ?
random->data : -1);
cout << "Data = " <<
temp->data << ", ";
cout << "Random Data = " <<
randomData << endl;
temp = temp->next;
}
cout << endl;
}
// Actual clone method which returns
// head reference of cloned linked
// list.
LinkedList* clone()
{
// Initialize two references,
// one with original list's head.
Node *origCurr = head;
Node *cloneCurr = NULL;
// Hash map which contains node
// to node mapping of original
// and clone linked list.
unordered_map<Node*, Node*> mymap;
// Traverse the original list and
// make a copy of that in the
// clone linked list.
while (origCurr != NULL)
{
cloneCurr = new Node(origCurr->data);
mymap[origCurr] = cloneCurr;
origCurr = origCurr->next;
}
// Adjusting the original list
// reference again.
origCurr = head;
// Traversal of original list again
// to adjust the next and random
// references of clone list using
// hash map.
while (origCurr != NULL)
{
cloneCurr = mymap[origCurr];
cloneCurr->next =
mymap[origCurr->next];
cloneCurr->random =
mymap[origCurr->random];
origCurr = origCurr->next;
}
// return the head reference of
// the clone list.
return new LinkedList(mymap[head]);
}
};
// Driver code
int main()
{
// Pushing data in the linked list.
LinkedList *mylist =
new LinkedList(new Node(5));
mylist->push(4);
mylist->push(3);
mylist->push(2);
mylist->push(1);
// Setting up random references.
mylist->head->random =
mylist->head->next->next;
mylist->head->next->random =
mylist->head->next->next->next;
mylist->head->next->next->random =
mylist->head->next->next->next->next;
mylist->head->next->next->next->random =
mylist->head->next->next->next->next->next;
mylist->head->next->next->next->next->random =
mylist->head->next;
// Making a clone of the original
// linked list.
LinkedList *clone = mylist->clone();
// Print the original and cloned
// linked list.
cout << "Original linked list";
mylist->print();
cout << "Cloned linked list";
clone->print();
}
// This code is contributed by Chhavi
Producción:
Original linked list Data = 1, Random data = 3 Data = 2, Random data = 4 Data = 3, Random data = 5 Data = 4, Random data = -1 Data = 5, Random data = 2 Cloned linked list Data = 1, Random data = 3 Data = 2, Random data = 4 Data = 3, Random data = 5 Data = 4, Random data = -1 Data = 5, Random data = 2
Complejidad de tiempo: O(n)
Espacio auxiliar : O(n)
Consulte el artículo completo sobre Clonar una lista enlazada con puntero siguiente y aleatorio | Set 2 para más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA