Meilleur algorithme pour tester si une liste liée a un cycle de

Question

Quel est le meilleur (arrêt) algorithme permettant de déterminer si une liste liée a un cycle en elle?

[Modifier] l'Analyse de la complexité asymptotique pour l'espace et le temps serait doux si des réponses peuvent être comparés mieux.

[Edit] Original question n'a pas à examiner les nœuds avec outdegree > 1, mais il y a un peu parler d'elle.Cette question est plus le long des lignes de "Meilleur algorithme pour détecter les cycles dans un graphe orienté".

Answer 1

Deux pointeurs parcourant la liste;faire un itérer à deux fois la vitesse de l'autre, et de comparer leurs positions à chaque étape.Sur le dessus 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 vous pouvez obtenir.

Answer 2

Condition:Garder une trace de la taille de la liste (mise à jour de la taille whenenver un nœud est ajouté ou supprimé).

La détection de boucle:

1. Garder un compteur lors de la traversée de la taille de la liste.

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

Complexité:O(n)

Note: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 doit être thread-safe.

Answer 3

Prendre 2 pointeur *p et *q , début de la traversée de la liste liée "LL" en utilisant les deux pointeurs :

1) pointeur p va supprimer le nœud précédent à chaque fois et en pointant au prochain nœud.

2) pointeur q va aller à chaque fois dans le sens de la marche seule direction.

conditions:

1) pointeur p pointe sur null et q est de pointage pour certains nœud :La boucle est présent

2) les deux pointeur pointant vers null:aucune boucle n'est-il

Answer 4

Que penser de l'utilisation d'une table de hachage pour stocker les déjà vu des nœuds (on les regarde dans l'ordre depuis le début de la liste)?Dans la pratique, vous pouvez obtenir quelque chose de proche de O(N).

Sinon, à l'aide d'une triés tas au lieu d'une table de hachage permettrait d'atteindre O(N log(N)).

Answer 5

Je me demande si il y a d'autre moyen que de simplement aller de manière itérative - remplir un tableau comme vous le pas vers l'avant et vérifier si le nœud actuel est déjà présent dans la table...

Answer 6

Konrad Rudolph algorithme ne fonctionne pas si le cycle n'est pas pointant vers le début.La liste suivante permettra de faire une boucle infinie:1->2->3->2.

DrPizza de l'algorithme est certainement le chemin à parcourir.

Answer 7

Dans ce cas OysterD code sera la solution la plus rapide (vertex colorier)

Ce serait vraiment une surprise pour moi.Ma solution fait plus de deux passes dans la liste (si le dernier nœud est lié à l'avant-dernière lode), et dans la plupart des cas (pas de boucle) ne feront qu'un passage.Sans malaxage, sans l'allocation de la mémoire, etc.

Answer 8

Dans ce cas OysterD code sera la solution la plus rapide (vertex colorier)

Ce serait vraiment une surprise pour moi.Ma solution fait plus de deux passes dans la liste (si le dernier nœud est lié à l'avant-dernière lode), et dans la plupart des cas (pas de boucle) ne feront qu'un passage.Sans malaxage, sans l'allocation de la mémoire, etc.

Oui.J'ai remarqué que la formulation n'était pas parfait et ont reformulé il.Je persiste à croire qu'un habile hachage peut effectuer plus rapidement par les cheveux.Je crois que votre algorithme est la meilleure solution, bien que.

Juste pour souligner mon point de vue:le vertec colorant est utilisé pour détecter les cycles de dépendances par les ramasseurs d'ordures, de sorte qu'il existe un véritable cas d'utilisation pour elle.Ils utilisent principalement des indicateurs de bits pour effectuer la coloration.

Answer 9

Vous aurez à visiter chaque nœud de le déterminer.Cela peut être fait de manière récursive.Pour vous arrêter visiter déjà visité les nœuds, vous avez besoin d'un drapeau pour dire "déjà visité".Bien sûr, cela ne vous donne pas de boucles.Ainsi, au lieu d'un drapeau d'un bit, l'utilisation d'un nombre.Commencer à 1.Vérifier les nœuds connectés et puis marquer ces 2 et de manière récursive jusqu'à ce que le réseau est couvert.Si lors de la vérification de nœuds que vous rencontrez un nœud qui est plus qu'un de moins que le nœud actuel, alors vous avez un cycle.La durée du cycle est donné par la différence.

Answer 10

Deux pointeurs sont initialisés à la tête de liste.Un pointeur avancer une fois à chaque étape, et de l'autre, avancer deux fois à chaque étape.Si la plus rapide du pointeur de la rencontre la plus lente encore une fois, il y a une boucle dans la liste.Sinon il n'y a pas de boucle si le plus vite on arrive à la fin de la liste.

L'exemple de code ci-dessous est mis en œuvre conformément à cette solution.Le plus rapide pointeur est pFast, et le plus lent est pSlow.

bool HasLoop(ListNode* pHead)
{
    if(pHead == NULL)
        return false;


    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == NULL)
        return false;


    ListNode* pFast = pSlow->m_pNext;
    while(pFast != NULL && pSlow != NULL)
    {
        if(pFast == pSlow)
            return true;


        pSlow = pSlow->m_pNext;


        pFast = pFast->m_pNext;
        if(pFast != NULL)
            pFast = pFast->m_pNext;
    }


    return false;
}

Cette solution est disponible sur mon blog.Il n'y a plus de problème discuté dans le blog:Qu'est-ce que le noeud d'entrée lorsqu'il est cycle/boucle dans une liste?

Answer 11

"Hack" de la solution (devrait fonctionner en C/C++):

• La traversée de la liste et définissez le dernier bit de next pointeur vers 1.
• Si un élément avec marqué pointeur -- retourne true et le premier élément du cycle.
• Avant de rentrer, réinitialisation des pointeurs, mais je crois déréférencement fonctionne même avec marqué pointeurs.

Complexité temporelle est 2n.Regarde comme elle ne temporelles variables.

Answer 12

C'est une solution en utilisant une table de Hachage ( juste une liste en fait) pour enregistrer l'adresse de pointeur.

def hash_cycle(node):
    hashl=[]
    while(node):
        if node in hashl:
            return True
        else:
            hashl.append(node)
            node=node.next
    return False

Answer 13

def has_cycle(à la tête):compteur = set()

while head is not None:
    if head in counter:
        return True
    else:
        counter.add(head)
        head = head.next