Maison > développement back-end > Golang > le corps du texte

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

WBOY
Libérer: 2024-07-17 09:11:29
original
361 Les gens l'ont consulté

Detect cycle in linked list

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
}
Copier après la connexion

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!

source:dev.to
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal