Dada una lista enlazada que tiene dos punteros en cada Node. El primero apunta al siguiente Node de la lista, sin embargo, el otro puntero es aleatorio y puede apuntar a cualquier Node de la lista. Escriba un programa que clone la lista dada en el espacio O(1), es decir, sin ningún espacio adicional.
Ejemplos:
Input : Head of the below-linked list
Output : A new linked list identical to the original list.
En las publicaciones anteriores, Set-1 y Set-2 se analizan varios métodos, y también está disponible la implementación de la complejidad del espacio O(n).
En esta publicación, implementaremos un algoritmo que no requerirá espacio adicional, como se explicó en el Conjunto 1.
A continuación se muestra el algoritmo:
- Cree la copia del Node 1 e insértela entre el Node 1 y el Node 2 en la lista enlazada original, cree una copia del 2 e insértela entre el 2 y el 3. Continúe de esta manera, agregue la copia de N después del enésimo Node
- Ahora copie el enlace aleatorio de esta manera
original->next->random= original->random->next; /*TRAVERSE TWO NODES*/
- Esto funciona porque original->siguiente no es más que una copia del original y Original->aleatorio->siguiente no es más que una copia del azar.
- Ahora restaure las listas enlazadas originales y copie de esta manera en un solo ciclo.
original->next = original->next->next;
copy->next = copy->next->next;
- Asegúrese de que original->next sea NULL y devuelva la lista clonada
A continuación se muestra la implementación.
Javascript
<script>
// Javascript program to clone a linked list with next
// and arbit pointers in O(n) time
// Structure of linked list Node
class Node {
constructor(x) {
this.data = x;
this.next = this.random = null;
}
}
// Utility function to print the list.
function print(start) {
var ptr = start;
while (ptr != null) {
document.write(
"Data = " +
ptr.data + ", Random = "
+ ptr.random.data+"<br/>"
);
ptr = ptr.next;
}
}
// This function clones a given
// linked list in O(1) space
function clone(start) {
var curr = start, temp = null;
// insert additional node after
// every node of original list
while (curr != null) {
temp = curr.next;
// Inserting node
curr.next = new Node(curr.data);
curr.next.next = temp;
curr = temp;
}
curr = start;
// adjust the random pointers of the
// newly added nodes
while (curr != null) {
if (curr.next != null)
curr.next.random = (curr.random != null) ?
curr.random.next : curr.random;
// move to the next newly added node by
// skipping an original node
curr = (curr.next != null) ?
curr.next.next : curr.next;
}
var original = start, copy = start.next;
// save the start of copied linked list
temp = copy;
// now separate the original list and copied list
while (original != null && copy != null) {
original.next = (original.next != null) ?
original.next.next : original.next;
copy.next = (copy.next != null) ?
copy.next.next : copy.next;
original = original.next;
copy = copy.next;
}
return temp;
}
// Driver code
var start = new Node(1);
start.next = new Node(2);
start.next.next = new Node(3);
start.next.next.next = new Node(4);
start.next.next.next.next = new Node(5);
// 1's random points to 3
start.random = start.next.next;
// 2's random points to 1
start.next.random = start;
// 3's and 4's random points to 5
start.next.next.random =
start.next.next.next.next;
start.next.next.next.random =
start.next.next.next.next;
// 5's random points to 2
start.next.next.next.next.random =
start.next;
document.write("Original list : <br/>");
print(start);
document.write("<br>");
document.write("Cloned list : <br/>");
var cloned_list = clone(start);
print(cloned_list);
// This code contributed by aashish1995
</script>
Original list : Data = 1, Random = 3 Data = 2, Random = 1 Data = 3, Random = 5 Data = 4, Random = 5 Data = 5, Random = 2 Cloned list : Data = 1, Random = 3 Data = 2, Random = 1 Data = 3, Random = 5 Data = 4, Random = 5 Data = 5, Random = 2
Complejidad de tiempo: O(n), donde n es el número de Nodes en la lista enlazada dada.
Espacio Auxiliar: O(1), ya que no se utiliza espacio extra. Los n Nodes que se insertan entre los Nodes ya se requerían para clonar la lista, por lo que podemos decir que no usamos ningún espacio adicional.
¡ Consulte el artículo completo sobre Clonar una lista enlazada con el puntero siguiente y aleatorio en el espacio O (1) para obtener 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