¿Cómo detectas un ciclo en una linked list con O(1) de espacio extra?
Opciones
- Guardar cada nodo visitado en un hash set y buscar repetidos
- Floyd: un puntero lento y uno rápido se encuentran si hay un ciclo (Opción correcta)
- Invertir la lista in place y compararla con la original
- Ordenar los nodos por valor y buscar nodos repetidos
Respuesta
La tortuga y la liebre de Floyd: el lento avanza 1, el rápido 2; se encuentran si hay un ciclo
Por qué
Usa dos punteros: el lento avanza 1 nodo por paso, el rápido 2 nodos.
Si la lista termina, no hay ciclo. Si HAY un ciclo, el puntero rápido acaba alcanzando al lento dentro del bucle y se encuentran, como dos corredores en una pista circular.
Un set de nodos visitados también funciona, pero usa O(n) de memoria.
Recuerda
Detección de ciclos: punteros rápido y lento.