Bestimmung, ob eine verknüpfte Liste einen Zyklus hat, indem man nur zwei Speicherplätze verwendet

Question

Kennt jemand einen Algorithmus, mit dem man herausfinden kann, ob eine verknüpfte Liste eine Schleife über sich selbst macht, indem man nur zwei Variablen verwendet, um die Liste zu durchlaufen. Angenommen, man hat eine verknüpfte Liste von Objekten, wobei es keine Rolle spielt, um welche Art von Objekt es sich handelt. Ich habe einen Zeiger auf den Kopf der verknüpften Liste in einer Variablen und ich habe nur eine andere Variable, mit der ich die Liste durchlaufen kann.

Mein Plan ist also, Zeigerwerte zu vergleichen, um zu sehen, ob irgendwelche Zeiger gleich sind. Die Liste ist von endlicher Größe, kann aber riesig sein. Ich kann beide Variablen auf den Kopf setzen und dann die Liste mit der anderen Variable durchlaufen, wobei ich immer prüfe, ob sie gleich der anderen Variable ist, aber wenn ich auf eine Schleife stoße, komme ich nicht mehr heraus. Ich denke, es hat mit den unterschiedlichen Geschwindigkeiten beim Durchlaufen der Liste und dem Vergleich der Zeigerwerte zu tun. Hat jemand eine Idee?

Answer 1

Ich würde vorschlagen, dass Sie Floyd's Cycle-Finding Algorithm alias Die Tortoise and the Hare Algorithm . Es hat eine O(n)-Komplexität und ich denke, es entspricht Ihren Anforderungen.

Beispiel-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;
}

Mehr Informationen auf Wikipedia: Floyd's Zyklusfindungsalgorithmus .

Answer 2

Sie können die Schildkröte und Kaninchen Algorithmus.

Wikipedia hat auch eine Erklärung und nennt sie " Floyd's Zyklusfindungsalgorithmus " oder "Schildkröte und Hase"

Answer 3

Unbedingt. Eine Lösung kann in der Tat darin bestehen, die Liste mit beiden Zeigern zu durchlaufen, wobei der eine mit der doppelten Geschwindigkeit des anderen läuft.

Beginnen Sie mit dem "langsamen" und dem "schnellen" Zeiger, die auf eine beliebige Stelle in der Liste zeigen. Führen Sie die Durchlaufschleife aus. Wenn der 'schnelle' Zeiger zu irgendeinem Zeitpunkt mit dem langsamen Zeiger übereinstimmt, haben Sie eine zirkulär verknüpfte Liste.

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

Ich habe versucht, dieses Problem selbst zu lösen, und habe eine andere (weniger effiziente, aber immer noch optimale) Lösung gefunden.

Die Idee basiert auf der Umkehrung einer einfach verketteten Liste in linearer Zeit. Dazu werden bei jedem Schritt der Iteration über die Liste zwei Vertauschungen vorgenommen. Wenn q das vorherige Element (anfangs Null) und p das aktuelle ist, dann wird swap(q,p->next) swap(p,q) die Verknüpfung umkehren und die beiden Zeiger gleichzeitig weiterschalten. Die Vertauschungen können mit XOR durchgeführt werden, um zu verhindern, dass eine dritte Speicherstelle verwendet werden muss.

Wenn die Liste einen Zyklus hat, wird man irgendwann während der Iteration an einem Knoten ankommen, dessen Zeiger bereits geändert wurde. Sie können nicht wissen, welcher Knoten das ist, aber wenn Sie die Iteration fortsetzen und dabei einige Elemente zweimal vertauschen, gelangen Sie wieder an den Kopf der Liste.

Wenn man die Liste zweimal umdreht, bleibt das Ergebnis unverändert und man kann erkennen, ob es einen Zyklus gab, je nachdem, ob man am ursprünglichen Kopf der Liste angekommen ist oder nicht.

Answer 5

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;
}