algorithm - has - Algoritmo de detección de bucle de lista enlazada

linked list cycle

Question

Leí una pregunta de una entrevista en línea sobre cómo encontrarías un bucle en una lista vinculada, y la solución ( el algoritmo de búsqueda de ciclos de Floyd ) es tener dos punteros, uno es 2 veces más rápido que el otro y verificar si se vuelven a encontrar.

Mi pregunta es: ¿por qué no puedo mantener un puntero fijo, solo mover el otro puntero hacia delante en 1 paso cada vez?

Answer 1

Debido a que el bucle puede no contener el elemento apuntado por el primer puntero.

Por ejemplo, si el primer puntero apunta al elemento 1 y la lista vinculada tiene un bucle más adelante (1-> 2-> 3-> 4-> 2), su algoritmo no lo detectará.

Answer 2

Debido a que el primer puntero (que no se mueve) podría no estar dentro del ciclo, por lo que los punteros nunca se encontrarían. (Recuerde que un ciclo puede consistir en solo una parte de la lista).

Answer 3

Porque quizás no la lista enlazada completa esté dentro del ciclo.

Para un algoritmo de detección de lazo enlazado, necesita dos punteros:

Mientras el primer puntero esté donde está el vaquero, no se detectará ningún lazo. Pero si lo mueve paso a paso hacia adelante, eventualmente ingresará al ciclo.

Por cierto, lasso es el término técnico de la teoría de grafos, vaquero no lo es.