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.
Java
// Java program to clone a linked list
// with random pointers
import java.util.HashMap;
import java.util.Map;
// Linked List Node class
class Node
{
// Node data
int data;
// Next and random reference
Node next, random;
// Node constructor
public Node(int data)
{
this.data = data;
this.next = this.random = null;
}
}
// Linked list class
class LinkedList
{
// Linked list head reference
Node head;
// Linked list constructor
public LinkedList(Node head)
{
this.head = head;
}
// Push method to put data always
// at the head in the linked list.
public void push(int data)
{
Node node = new Node(data);
node.next = this.head;
this.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);
System.out.println("Data = " + temp.data +
", Random data = " +
randomData);
temp = temp.next;
}
}
// Actual clone method which returns head
// reference of cloned linked list.
public LinkedList clone()
{
// Initialize two references, one with
// original list's head.
Node origCurr = this.head,
cloneCurr = null;
// Hash map which contains node to node
// mapping of original and clone linked list.
Map<Node, Node> map = new HashMap<Node, Node>();
// Traverse the original list and make a
// copy of that in the clone linked list.
while (origCurr != null)
{
cloneCurr = new Node(origCurr.data);
map.put(origCurr, cloneCurr);
origCurr = origCurr.next;
}
// Adjusting the original list
// reference again.
origCurr = this.head;
// Traversal of original list again to
// adjust the next and random references
// of clone list using hash map.
while (origCurr != null)
{
cloneCurr = map.get(origCurr);
cloneCurr.next =
map.get(origCurr.next);
cloneCurr.random =
map.get(origCurr.random);
origCurr = origCurr.next;
}
// Return the head reference of the
// clone list.
return new LinkedList(map.get(this.head));
}
}
// Driver Class
class Main
{
// Main method.
public static void main(String[] args)
{
// Pushing data in the linked list.
LinkedList list =
new LinkedList(new Node(5));
list.push(4);
list.push(3);
list.push(2);
list.push(1);
// Setting up random references.
list.head.random =
list.head.next.next;
list.head.next.random =
list.head.next.next.next;
list.head.next.next.random =
list.head.next.next.next.next;
list.head.next.next.next.random =
list.head.next.next.next.next.next;
list.head.next.next.next.next.random =
list.head.next;
// Making a clone of the original
// linked list.
LinkedList clone = list.clone();
// Print the original and cloned
// linked list.
System.out.println(
"Original linked list");
list.print();
System.out.println(
"Cloned linked list");
clone.print();
}
}
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