Leí una pregunta de una entrevista en línea sobre cómo encontraría un bucle en una lista vinculada, y la solución (algoritmo de búsqueda de ciclos de Floyd) es tener dos punteros, uno es 2 veces más rápido que el otro , y verifica si se encuentran nuevamente.Algoritmo de detección de bucle de lista enlazada
Mi pregunta es: ¿por qué no puedo mantener un puntero fijo, solo mover el otro puntero hacia delante en 1 paso cada vez?
Porque el primer puntero (que no se mueve) podría no estar dentro del bucle, por lo que los punteros nunca se encontrarían. (Recuerde que un bucle puede consistir en solo una parte de la lista.)
Eso lo aclara. Gracias a todos, ya que solo puedo marcar una respuesta correcta, marcaré la primera. –
Porque el bucle puede no contener el elemento al que apunta 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á.
acabo de eliminar algunos errores menores de ortografía así puedo darte los 50+ en una semana con buena conciencia (ya que te perdiste de ser aceptado por un par de segundos). – DaveFar
@DaveBall Wow. Gracias. Me alegro de que lo hayas notado. ;) – quasiverse
Porque quizás no todo el linkedList esté dentro del ciclo.
Para una lista enlazada lazo algoritmo de detección, se necesitan dos punteros:
Mientras el primer puntero es donde el vaquero es, no se detecta ningún bucle. Pero si lo mueve paso a paso hacia adelante, eventualmente ingresará al ciclo.
BTW, lasso es el término técnico de la teoría de grafos, vaquero no lo es.
Hay una modificación algo más rápida del algoritmo, si alguien tiene curiosidad: http://www.siafoo.net/algorithm/11 – Dave