Dada una lista enlazada individualmente, elimine la mitad de la lista enlazada. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5, entonces la lista enlazada debe modificarse a 1->2->4->5
Si hay Nodes pares, entonces habría dos Nodes intermedios, debemos eliminar el segundo elemento intermedio. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5->6, entonces debe modificarse a 1->2->3->5->6.
Si la lista enlazada de entrada es NULL, entonces debería permanecer NULL.
Si la lista enlazada de entrada tiene 1 Node, entonces este Node debe eliminarse y debe devolverse un nuevo encabezado.
Solución eficiente:
Enfoque: La solución anterior requiere dos recorridos de la lista enlazada. El Node medio se puede eliminar usando un recorrido. La idea es usar dos punteros, slow_ptr y fast_ptr. Ambos punteros comienzan desde el encabezado de la lista. Cuando fast_ptr llega al final, slow_ptr llega al medio. Esta idea es la misma que la utilizada en el método 2 de esta publicación. Lo adicional en esta publicación es realizar un seguimiento del medio anterior para que se pueda eliminar el Node medio.
A continuación se muestra la implementación.
Javascript
<script>
// Javascript program to delete the
// middle of a linked list
// Link list Node
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
}
// Deletes middle node and returns
// head of the modified list
function deleteMid( head)
{
// Base cases
if (head == null)
return null;
if (head.next == null)
{
return null;
}
// Initialize slow and fast pointers
// to reach middle of linked list
var slow_ptr = head;
var fast_ptr = head;
// Find the middle and previous of
// middle.
var prev = null;
// To store previous of slow_ptr
while (fast_ptr != null &&
fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
prev = slow_ptr;
slow_ptr = slow_ptr.next;
}
// Delete the middle node
prev.next = slow_ptr.next;
return head;
}
// A utility function to print
// a given linked list
function printList(ptr)
{
while (ptr != null)
{
document.write(ptr.data + "->");
ptr = ptr.next;
}
document.write("NULL<br/>");
}
// Utility function to create a
// new node.
function newNode(data)
{
temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Driver code
// Start with the empty list
head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(3);
head.next.next.next = newNode(4);
document.write("Given Linked List<br/>");
printList(head);
head = deleteMid(head);
document.write(
"Linked List after deletion of middle<br/>");
printList(head);
// This code is contributed by umadevi9616
</script>
Producción:
Given Linked List 1->2->3->4->NULL Linked List after deletion of middle 1->2->4->NULL
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesita un recorrido de la lista enlazada - Espacio Auxiliar: O(1).
Como no se necesita espacio adicional.
¡Consulte el artículo completo sobre Eliminar el medio de la lista vinculada 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