Programa Java para eliminar la mitad de la lista vinculada

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 simple: la idea es primero contar el número de Nodes en una lista enlazada, luego eliminar el Node n/2 usando el proceso de eliminación simple. 

// Java program to delete middle
// of a linked list
import java.io.*;
class GFG {
  
    // Link list Node 
    static class Node 
    {
        int data;
        Node next;
    }
  
    // Utility function to create 
    // a new node.
    static Node newNode(int data)
    {
        Node temp = new Node();
        temp.data = data;
        temp.next = null;
        return temp;
    }
  
    // Count of nodes
    static int countOfNodes(Node head)
    {
        int count = 0;
        while (head != null) 
        {
            head = head.next;
            count++;
        }
        return count;
    }
  
    // Deletes middle node and returns
    // head of the modified list
    static Node deleteMid(Node head)
    {
        // Base cases
        if (head == null)
            return null;
        if (head.next == null) 
        {
            return null;
        }
        Node copyHead = head;
  
        // Find the count of nodes
        int count = countOfNodes(head);
  
        // Find the middle node
        int mid = count / 2;
  
        // Delete the middle node
        while (mid-- > 1) 
        {
            head = head.next;
        }
  
        // Delete the middle node
        head.next = head.next.next;
  
        return copyHead;
    }
  
    // A utility function to print
    // a given linked list
    static void printList(Node ptr)
    {
        while (ptr != null) 
        {
            System.out.print(ptr.data + 
                             "->");
            ptr = ptr.next;
        }
        System.out.println("NULL");
    }
  
    // Driver code
    public static void main(String[] args)
    {
        // Start with the empty list 
        Node head = newNode(1);
        head.next = newNode(2);
        head.next.next = newNode(3);
        head.next.next.next = newNode(4);
  
        System.out.println("Given Linked List");
        printList(head);
        head = deleteMid(head);
        System.out.println(
               "Linked List after deletion of middle");
        printList(head);
    }
}
// This code is contributed by rajsanghavi9

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). 
  Se necesitan dos recorridos de la lista enlazada
• Espacio Auxiliar: O(1). 
  No se necesita espacio adicional.

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.  

// Java program to delete the 
// middle of a linked list
class GfG 
{
    // Link list Node 
    static class Node 
    {
        int data;
        Node next;
    }
  
    // Deletes middle node and returns
    // head of the modified list
    static Node deleteMid(Node 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
        Node slow_ptr = head;
        Node fast_ptr = head;
  
        // Find the middle and previous 
        // of middle.
        Node 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
    static void printList(Node ptr)
    {
        while (ptr != null) 
        {
            System.out.print(ptr.data + "->");
            ptr = ptr.next;
        }
        System.out.println("NULL");
    }
  
    // Utility function to create a 
    // new node.
    static Node newNode(int data)
    {
        Node temp = new Node();
        temp.data = data;
        temp.next = null;
        return temp;
    }
  
    // Driver code
    public static void main(String[] args)
    {
        // Start with the empty list 
        Node head = newNode(1);
        head.next = newNode(2);
        head.next.next = newNode(3);
        head.next.next.next = newNode(4);
  
        System.out.println("Given Linked List");
        printList(head);
        head = deleteMid(head);
        System.out.println("Linked List after deletion of middle");
        printList(head);
    }
}
// This code is contributed by Prerna saini

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!