#code #algorithme

Il y a deux principaux algorithmes pour détecter un cycle (dans une linked list, par exemple) : - Avec un hashset - Avec l’algorithme de Floyd (Tortoise and Hare Alorithm)

Avec un hashset, il suffit de noter les nodes visitées dans le hashset. Si une nouvelle node est déjà présente dans le hashset, alors il y a un cycle. Cet algorithme est 0(n) en temps et en espace.

Avec l’algorithme de Floyd, deux “pointeurs” sont utilisés et parcourent la liste. Un pointeur (le lapin) avance deux fois plus vite que le deuxième (la tortue). Si il y a un cycle, alors la tortue et le lapin finiront par se retrouver au même point. Il est ensuite possible de calculer le point de départ du cycle, si besoin.