Programa C para encontrar el elemento medio de una lista enlazada dada

Dada una lista enlazada individualmente, busque el centro de la lista enlazada. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5, entonces la salida debería ser 3. 
Si hay Nodes pares, entonces habría dos Nodes intermedios, necesitamos imprimir el segundo intermedio. elemento. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5->6, entonces la salida debería ser 4. 

Método 1: 
recorrer toda la lista enlazada y contar el no. de Nodes Ahora recorra la lista nuevamente hasta la cuenta/2 y devuelva el Node en la cuenta/2. 

Método 2: 
recorrer la lista enlazada usando dos punteros. Mueva un puntero por uno y los otros punteros por dos. Cuando el puntero rápido llegue al final, el puntero lento llegará a la mitad de la lista enlazada.

La siguiente imagen muestra cómo funciona la función printMiddle en el código:

// C program to find middle of linked list
#include<stdio.h>
#include<stdlib.h>
 
// Link list node
struct Node
{
    int data;
    struct Node* next;
};
 
// Function to get the middle of
// the linked list
void printMiddle(struct Node *head)
{
    struct Node *slow_ptr = head;
    struct Node *fast_ptr = head;
 
    if (head!=NULL)
    {
        while (fast_ptr != NULL &&
               fast_ptr->next != NULL)
        {
            fast_ptr = fast_ptr->next->next;
            slow_ptr = slow_ptr->next;
        }
        printf("The middle element is [%d]",
                slow_ptr->data);
    }
}
 
void push(struct Node** head_ref,
          int new_data)
{
    // Allocate node
    struct Node* new_node =
           (struct Node*) malloc(sizeof(struct Node));
 
    // Put in the data
    new_node->data = new_data;
 
    // Link the old list off the new node
    new_node->next = (*head_ref);
 
    // Move the head to point to the new node
    (*head_ref) = new_node;
}
 
// A utility function to print a given
//  linked list
void printList(struct Node *ptr)
{
    while (ptr != NULL)
    {
        printf("%d->", ptr->data);
        ptr = ptr->next;
    }
    printf("NULL");
}
 
// Driver code
int main()
{
    // Start with the empty list
    struct Node* head = NULL;
    int i;
 
    for (i = 5; i > 0; i--)
    {
        push(&head, i);
        printList(head);
        printMiddle(head);
    }
    return 0;
}

Producción:

5->NULL
The middle element is [5]

4->5->NULL
The middle element is [5]

3->4->5->NULL
The middle element is [4]

2->3->4->5->NULL
The middle element is [4]

1->2->3->4->5->NULL
The middle element is [3]

Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.

Método 3: 
Inicialice el elemento medio como cabeza e inicialice un contador como 0. Recorra la lista desde la cabeza, mientras recorre incremente el contador y cambie de mitad a mitad->siguiente siempre que el contador sea impar. Entonces, el medio se moverá solo la mitad de la longitud total de la lista. 
Gracias a Narendra Kangralkar por sugerir este método. 

// C program to implement the
// above approach
#include <stdio.h>
#include <stdlib.h>
 
// Link list node
struct node
{
    int data;
    struct node* next;
};
 
// Function to get the middle of
// the linked list
void printMiddle(struct node* head)
{
    int count = 0;
    struct node* mid = head;
 
    while (head != NULL)
    {
        // Update mid, when 'count'
        // is odd number
        if (count & 1)
            mid = mid->next;
 
        ++count;
        head = head->next;
    }
 
    // If empty list is provided
    if (mid != NULL)
        printf("The middle element is [%d]",
                mid->data);
}
 
void push(struct node** head_ref,
          int new_data)
{
    // Allocate node
    struct node* new_node =
           (struct node*)malloc(sizeof(struct node));
 
    // Put in the data 
    new_node->data = new_data;
 
    // Link the old list off the new node
    new_node->next = (*head_ref);
 
    // Move the head to point to the new node
    (*head_ref) = new_node;
}
 
// A utility function to print a
// given linked list
void printList(struct node* ptr)
{
    while (ptr != NULL)
    {
        printf("%d->", ptr->data);
        ptr = ptr->next;
    }
    printf("NULL");
}
 
// Driver code
int main()
{
    // Start with the empty list
    struct node* head = NULL;
    int i;
 
    for (i = 5; i > 0; i--)
    {
        push(&head, i);
        printList(head);
        printMiddle(head);
    }
    return 0;
}

Producción:

5->NULL
The middle element is [5]

4->5->NULL
The middle element is [5]

3->4->5->NULL
The middle element is [4]

2->3->4->5->NULL
The middle element is [4]

1->2->3->4->5->NULL
The middle element is [3]

Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.

¡ Consulte el artículo completo sobre Encontrar el medio de una lista vinculada dada para obtener más detalles!