Programa C++ 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. 

// C++ program to delete middle
// of a linked list
#include <bits/stdc++.h>
using namespace std;
  
// Link list Node 
struct Node 
{
    int data;
    struct Node* next;
};
  
// Count of nodes
int countOfNodes(struct Node* head)
{
    int count = 0;
    while (head != NULL) 
    {
        head = head->next;
        count++;
    }
    return count;
}
  
// Deletes middle node and returns
// head of the modified list
struct Node* deleteMid(struct Node* head)
{
    // Base cases
    if (head == NULL)
        return NULL;
    if (head->next == NULL) 
    {
        delete head;
        return NULL;
    }
    struct 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
void printList(struct Node* ptr)
{
    while (ptr != NULL) 
    {
        cout << ptr->data << "->";
        ptr = ptr->next;
    }
    cout << "NULL";
}
  
// Utility function to create 
// a new node.
Node* newNode(int data)
{
    struct Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}
  
// Driver code
int main()
{
    // Start with the empty list 
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
  
    cout << "Given Linked List";
    printList(head);
    head = deleteMid(head);
    cout << "Linked List after deletion of middle";
    printList(head);
    return 0;
}

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.  

// C++ program to delete middle
// of a linked list
#include <bits/stdc++.h>
using namespace std;
  
// Link list Node 
struct Node 
{
    int data;
    struct Node* next;
};
  
// Deletes middle node and returns 
// head of the modified list
struct Node* deleteMid(struct Node* head)
{
    // Base cases
    if (head == NULL)
        return NULL;
    if (head->next == NULL) 
    {
        delete head;
        return NULL;
    }
  
    // Initialize slow and fast pointers
    // to reach middle of linked list
    struct Node* slow_ptr = head;
    struct Node* fast_ptr = head;
  
    // Find the middle and previous 
    // of middle.
    // To store previous of slow_ptr    
    struct Node* prev; 
    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;
    delete slow_ptr;
  
    return head;
}
  
// A utility function to print 
// a given linked list
void printList(struct Node* ptr)
{
    while (ptr != NULL) 
    {
        cout << ptr->data << "->";
        ptr = ptr->next;
    }
    cout << "NULL";
}
  
// Utility function to create 
// a new node.
Node* newNode(int data)
{
    struct Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}
  
// Driver code
int main()
{
    // Start with the empty list 
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
  
    cout << "Given Linked List";
    printList(head);
    head = deleteMid(head);
    cout << "Linked List after deletion of middle";
    printList(head);
    return 0;
}

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!