Détecter le cycle dans la liste chaînée

Un autre algorithme de liste chaînée.

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

Ce n’est en fait pas si mal. Il existe au moins 3 façons différentes de le faire en O(n).

Le moyen le plus simple consiste à modifier le nœud de la liste chaînée pour inclure un indicateur qui indique si un nœud a été visité. Au fur et à mesure que la liste est parcourue, si nous rencontrons un nœud qui a été visité alors il y a un cycle.

Une autre technique utilise une hashmap contenant les nœuds visités ou des références à ceux-ci. Au fur et à mesure que la liste est parcourue, les nœuds, ou leurs références, sont insérés dans le hachage. Si nous rencontrons un nœud déjà représenté dans le hashmap, alors un cycle existe. Bien que cette technique ne nécessite qu'un seul parcours, elle nécessite plus de mémoire en raison du hashmap.

Pour cet article, je vais utiliser l'algorithme de Floyd pour détecter le cycle. C'est assez simple.

func DetectCycle[T any](ll *LinkedList[T]) bool {
    slow := ll.Head
    fast := ll.Head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            return true
        }
    }
    return false
}

Cette technique utilise 2 pointeurs dans la liste. Au fur et à mesure que la liste est parcourue, un pointeur déplace un nœud à la fois et l'autre déplace deux nœuds à la fois. Si jamais les 2 pointeurs se rencontrent, un cycle existe.

Pourquoi ça marche ? Au fur et à mesure que la liste est parcourue, la distance entre les deux pointeurs augmente. S'il y a un cycle, le pointeur rapide « chevauchera » le pointeur lent.

Existe-t-il une mise en œuvre plus efficace ? Des conditions aux limites manquent-elles ? Faites-le-moi savoir dans les commentaires.

Merci !

Le code de cet article et de tous les articles de cette série peut être trouvé ici

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!