Detecção de ciclo de Floyd encontra um loop em uma sequência (como uma lista encadeada) usando dois ponteiros movendo em velocidades diferentes. Se um ciclo existe, o ponteiro rápido eventualmente alcança e se encontra com o lento. Usa O(1) de espaço extra.
Mova um ponteiro lento um passo e um ponteiro rápido dois passos. Em um ciclo, o intervalo diminui em um a cada passo, então eles devem colidir; sem um ciclo, o rápido atinge o fim.
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
Uma abordagem com hash-set também funciona, mas custa O(n) de espaço; Floyd usa espaço constante.
Use para detecção de loop em lista encadeada, encontrar o início do ciclo e detectar ciclos em grafos funcionais (cada nó tem um sucessor). Sempre proteja fast.next para evitar desreferências nulas. Para grafos gerais, use DFS com uma pilha de recursão.
Detectar ciclos é essencial para travessia segura — um loop não detectado significa iteração infinita.
O algoritmo de Floyd é um exemplo bonito de resolver um problema de espaço O(n) em espaço O(1) com um invariante inteligente.
Aparece em entrevistas de lista encadeada e na detecção de loops infinitos em máquinas de estado e sequências numéricas.