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

boolean findCircular(Node *head)
{
    Node *slower, * faster;
    slower = head;
    faster = head->next;
    while(true) {
        if ( !faster || !faster->next)
            return false;
        else if (faster == slower || faster->next == slower)
            return true;
        else
            faster = faster->next->next;
    }
}

Answer 2

Der nächste Schritt bei diesem Problem ist die Identifizierung des Zyklus (d. h. nicht nur, dass der Zyklus existiert, sondern auch, wo genau er sich in der Liste befindet). Der Algorithmus "Schildkröte und Hase" kann dafür verwendet werden, allerdings müssen wir den Kopf der Liste immer im Auge behalten. Eine Illustration dieses Algorithmus finden Sie unter aquí .