¿Cómo determinar si una lista vinculada contiene un bucle?

duplicados posibles:
find whether a loop in a linked list without two pointers
How to determine if a linked list has a cycle using only two memory locations.
Best algorithm to test if a linked list has a cycle ¿Cómo determinar si una lista vinculada contiene un bucle?

Durante una preparación para una entrevista de trabajo, me encontré con la siguiente pregunta:

¿Cómo se puede determinar si una lista enlazada (de cualquier tipo) contiene un bucle, usando additio complejidad del espacio nal de O (1)? No puede suponer que el ciclo comienza en el primer nodo (y, por supuesto, el ciclo no tiene que contener todos los nodos).

no pude encontrar la respuesta, aunque no tengo la sensación de que es muy simple ...

Fuente

2010-06-08 ET.

Me perdí esta pregunta exacta en una entrevista. Solo pude dar la solución de memoria y tiempo O (* n *). – Thanatos

Me enteré de esto en una clase de CS, pero no creo que sea una buena pregunta, ya que es "solo obvio si ya lo sabes". –

Muchos, muchos duplicados, p. Ej. [busque si un bucle en una lista vinculada sin dos punteros] (http://stackoverflow.com/questions/2338683/find-whether-a-loop-in-a-linked-list-without-two-pointers) –

fácil. Mantenga dos punteros en la lista. En cada paso, avance un puntero por un solo enlace y avance el otro por dos enlaces. Prueba para ver si apuntan al mismo elemento. Si es así, tienes un bucle. Si no, repite hasta que encuentres un ciclo o llegues al final de la lista.

Fuente

2010-06-08 22:18:54 dty

+11

Descubrí que esta solución era solo "fácil" si lo sabía. Esto es, en mi opinión, un pensamiento bastante inteligente. – Thanatos

Interesante. ¿Por qué molestarse en adelantar al otro? –

Cualquier enlace puede ser igual a cualquier otro enlace, por lo que ambos deben moverse por la lista para probar cada combinación (alcanzable). – Ether

Probablemente la misma técnica que verificando si un gráfico es un árbol (los árboles no tienen ciclos), ver this this question. Recomienda un tipo topológico o una primera búsqueda en profundidad.

Fuente

2010-06-08 22:23:31 zdav

-1

Tuve este problema exacto en el código real la semana pasada.

Todo lo que hice fue mantener un puntero (enlace) para el primer elemento. Luego, mientras repetía la lista, si volvía a obtener ese puntero, sé que hay un ciclo.

Fuente

2010-06-08 22:38:52

Consulte los comentarios sobre la respuesta aceptada de por qué esto no captará * todos * los ciclos, y por qué esa es una solución mejor. –

El ciclo no necesariamente comienza en el primer elemento. –

¿Cómo determinar si una lista vinculada contiene un bucle?

Respuesta

Cuestiones relacionadas