La detección de ciclos de Floyd encuentra un bucle en una secuencia (como una lista enlazada) usando dos punteros que se mueven a diferentes velocidades. Si existe un ciclo, el puntero rápido eventualmente alcanza y se encuentra con el puntero lento. Usa O(1) espacio extra.
Mueve un puntero slow un paso y un puntero fast dos pasos. En un ciclo, la brecha se reduce en uno en cada paso, por lo que deben colisionar; sin un ciclo, el puntero rápido llega al final.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # +1 step
fast = fast.next.next # +2 steps
if slow is fast: # pointers met -> cycle
return True
return False # fast hit the end -> no cycle
Un enfoque de conjunto hash también funciona pero cuesta O(n) espacio; Floyd's usa espacio constante.
Usa para detección de bucles en lista enlazada, encontrar el inicio del ciclo y detectar ciclos en grafos funcionales (cada nodo tiene un sucesor). Siempre protege fast.next para evitar desreferencias nulas. Para grafos generales, usa DFS con una pila de recursión en su lugar.
La detección de ciclos es esencial para un traversal seguro — un bucle no detectado significa iteración infinita.
El algoritmo de Floyd es un hermoso ejemplo de resolver un problema de espacio O(n) en espacio O(1) con un invariante ingenioso.
Aparece en entrevistas de listas enlazadas y en la detección de bucles infinitos en máquinas de estado y secuencias numéricas.