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
// 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
// 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!
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