Comment déterminer si une liste chaînée a un cycle utilisant seulement deux emplacements de mémoire

Question

Quelqu'un sait-il d'un algorithme pour trouver si une liste liée boucle sur lui-même à l'aide de seulement deux variables pour parcourir la liste. Disons que vous avez une liste chaînée d'objets, il n'a pas d'importance quel type d'objet. J'ai un pointeur vers la tête de la liste liée dans une variable et je suis une autre variable pour parcourir la liste avec.

Donc mon plan est de comparer les valeurs de pointeur pour voir si tous les pointeurs sont les mêmes. La liste est de taille finie, mais peut être énorme. Je peux mettre les deux variables à la tête, puis la traversée de la liste avec les autres variables, de toujours vérifier si il est égal à l'autre variable, mais, si je ne frappe pas une boucle, je ne serai jamais en sortir. Je pense qu'il y a à faire, avec des taux différents de la traversée de la liste et en comparant les valeurs de pointeur. Toutes les pensées?

Answer 1

Je suggère d' utiliser Floyd's Cycle-Finding Algorithm aka The Tortoise and the Hare Algorithm . Il est très complexe et je pense que cela correspond à vos besoins.

Exemple de code:

 function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}
 

Plus d'informations sur Wikipedia: l'algorithme de recherche de cycle de Floyd .

Answer 2

Vous pouvez utiliser l'algorithme Turtle and Rabbit .

Wikipedia a aussi une explication, et ils l'appellent " l'algorithme de recherche de cycle de Floyd " ou "Tortoise et lièvre"

Answer 3

Absolument. Une solution peut en effet parcourir la liste avec les deux pointeurs, l'un voyageant deux fois plus vite que l'autre.

Commencez par le pointeur 'lent' et le pointeur 'rapide' pointant vers n'importe quel emplacement de la liste. Exécutez la boucle de traversée. Si le pointeur «rapide» coïncide à un moment quelconque avec le pointeur lent, vous avez une liste chaînée circulaire.

 int *head = list.GetHead();
if (head != null) {
    int *fastPtr = head;
    int *slowPtr = head;

    bool isCircular = true;

    do 
    {
        if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
        {
            isCircular = false;
            break;
        }

        fastPtr = fastPtr->Next->Next;
        slowPtr = slowPtr->Next;
    } while (fastPtr != slowPtr);

    //Do whatever you want with the 'isCircular' flag here
}
 

Answer 4

int isListCircular(ListNode* head){
    if(head==NULL)
        return 0;
    ListNode *fast=head, *slow=head;
    while(fast && fast->next){
        if(fast->next->next==slow)
            return 1;
        fast=fast->next->next;
        slow=slow->next;
    }
    return 0;
}