Détecter un cycle dans une liste chaînée

It is easier to port a shell than a shell script.

— Larry Wall

Dans la catégorie des problèmes qui ne se démodent pas, la détection d'un cycle dans une liste chaînée détient certainement une place de choix.[1]

Une solution simple consiste à traverser la liste tout en marquant chaque nœud visité. Si un nœud est déjà marqué lorsque l'algorithme le visite, alors nous pouvons conclure qu'un cycle existe. Cette approche à l'inconvénient de nécessiter la modification des nœuds de la liste chaînée pour être applicable. Néanmoins, la complexité de cet algorithme, O(n), est optimale.

Pour éviter de modifier les nœuds composant la liste chaînée, une table de hachage pourrait être utilisée afin de stocker des pointeurs vers les nœuds déjà visités. L'algorithme demanderait alors O(n) espace de stockage additionnel.

Il existe toutefois une solution qui ne demande aucun espace additionnel, aucune modification aux nœuds et qui s'exécute également en O(n): l'algorithme du lièvre et de la tortue. Il s'agit simplement de visiter la liste chaînée avec deux pointeurs, un lent — la tortue — et un rapide — le lièvre. Si un cycle existe, inévitablement, le lièvre rattrapera la tortue. Si aucun cycle n'existe, alors le lièvre atteindra tout simplement la fin de la liste.

int find_cycle(struct Node* head) {
    struct Node* tortoise, *hare1, *hare2;

    tortoise = head;
    hare1 = tortoise;

    while (tortoise && (hare2 = hare1->next) && (hare1 = hare2->next)) {
        if (hare1 == tortoise || hare2 == tortoise) {
            return 1;
        }
        tortoise = tortoise->next;
    }

    return 0;
}

Cet algorithme a été publiée pour la première fois en 1966 par Robert W. Floyd dans «Non-deterministic Algorithms» (pdf).