La détection de cycle de Floyd trouve une boucle dans une séquence (comme une liste chaînée) en utilisant deux pointeurs se déplaçant à des vitesses différentes. Si un cycle existe, le pointeur rapide finit par rattraper et rencontre le pointeur lent. Elle utilise O(1) d'espace supplémentaire.
Déplacez un pointeur slow d'une étape et un pointeur fast de deux étapes. Dans un cycle, l'écart diminue d'un à chaque étape, ils doivent donc entrer en collision ; sans cycle, fast atteint la fin.
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
Une approche avec hash-set fonctionne aussi mais coûte O(n) d'espace ; Floyd's utilise un espace constant.
À utiliser pour la détection de boucle de liste chaînée, trouver le début du cycle, et détecter les cycles dans les graphes fonctionnels (chaque nœud a un successeur). Toujours protéger fast.next pour éviter les déréférences null. Pour les graphes généraux, utilisez DFS avec une pile de récursion à la place.
Détecter les cycles est essentiel pour une traversée sécurisée — une boucle non détectée signifie une itération infinie.
L'algorithme de Floyd est un bel exemple de résolution d'un problème O(n)-espace en O(1) espace avec un invariant astucieux.
Il apparaît dans les interviews de liste chaînée et dans la détection de boucles infinies dans les machines d'état et les séquences de nombres.