Dada una lista enlazada, compruebe si la lista enlazada tiene un bucle o no. El siguiente diagrama muestra una lista enlazada con un bucle.
Solución
: enfoque del algoritmo de búsqueda de ciclos de Floyd : este es el método más rápido y se describe a continuación:
- Recorra la lista enlazada usando dos punteros.
- Mueva un puntero (slow_p) por uno y otro puntero (fast_p) por dos.
- Si estos punteros se encuentran en el mismo Node, entonces hay un bucle. Si los punteros no se encuentran, la lista enlazada no tiene un bucle.
La siguiente imagen muestra cómo funciona la función detectloop en el código:
Implementación del algoritmo de búsqueda de ciclos de Floyd:
C
// C program to detect loop in a linked list
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
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;
}
int detectLoop(struct Node* list)
{
struct Node *slow_p = list, *fast_p = list;
while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p) {
return 1;
}
}
return 0;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
/* Create a loop for testing */
head->next->next->next->next = head;
if (detectLoop(head))
printf("Loop found");
else
printf("No Loop");
return 0;
}
Loop found
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesita un recorrido del bucle. - Espacio Auxiliar: O(1).
No se requiere espacio.
¿Cómo funciona el algoritmo anterior?
Consulte: ¿Cómo funciona el enfoque de punteros rápidos y lentos de Floyd?
https://www.youtube.com/watch?v=Aup0kOWoMVg
Consulte el artículo completo sobre Detectar bucle en una 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