Meilleur algorithme pour tester si une liste chaînée a un cycle

Question

Quel est le meilleur algorithme (d'arrêt) pour déterminer si une liste chaînée contient un cycle?

[Modifier] L'analyse de la complexité asymptotique à la fois dans le temps et dans l'espace serait agréable pour que les réponses puissent être mieux comparées.

[Modifier] La question d'origine ne concernait pas les nœuds avec un degré supérieur à 1, mais il en est question. Cette question s'inscrit davantage dans la lignée du "Meilleur algorithme pour détecter les cycles dans un graphe orienté".

Answer 1

Demandez à deux pointeurs de parcourir la liste; faire parcourir deux fois la vitesse de l'autre et comparer leurs positions à chaque étape. Du haut de ma tête, quelque chose comme:

 node* tortoise(begin), hare(begin);
while(hare = hare->next)
{
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    hare = hare->next;
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    tortoise = tortoise->next;
}
 

O (n), qui est aussi bon que possible.

Answer 2

Condition préalable: garder une trace de la taille de la liste (mettre à jour la taille chaque fois qu'un nœud est ajouté ou supprimé).

Détection de boucle:

1. Gardez un compteur lorsque vous parcourez la taille de la liste.

2. Si le compteur dépasse la taille de la liste, il y a un cycle possible.

Complexité: O (n)

Remarque: la comparaison entre le compteur et la taille de la liste, ainsi que l'opération de mise à jour de la taille de la liste, doivent être rendues thread-safe.

Answer 3

Qu'en est-il de l'utilisation d'une table de hachage pour stocker les nœuds déjà vus (vous les regardez dans l'ordre depuis le début de la liste)? En pratique, vous pourriez réaliser quelque chose près de O (N).

Sinon, l'utilisation d'un tas trié au lieu d'une table de hachage permettrait d'obtenir O (N log (N)).

Answer 4

Je me demande s'il n'y a pas d'autre moyen que de procéder de manière itérative - remplissez un tableau lorsque vous avancez et vérifiez si le nœud actuel est déjà présent dans le tableau ...

Answer 5

L'algorithme de Konrad Rudolph ne fonctionnera pas si le cycle ne pointe pas vers le début. La liste suivante en fera une boucle infinie: 1-> 2-> 3-> 2.

L'algorithme de DrPizza est définitivement la voie à suivre.