Schleifen in verknüpften Listen mithilfe des Floyd-Algorithmus erkennen

Die Feststellung, ob eine bestimmte verknüpfte Liste eine Schleife enthält, kann in der Java-Programmierung eine anspruchsvolle Aufgabe sein. Eine Schleife tritt auf, wenn der letzte Knoten in der Liste auf einen vorherigen Knoten verweist, anstatt eine Nullreferenz zu haben.

Um Schleifen effizient zu erkennen, verwenden Entwickler häufig Floyds Zyklusfindungsalgorithmus, auch bekannt als Tortoise-and-Hare-Algorithmus . Dieser Algorithmus verwendet zwei Referenzen, eine langsame und eine schnelle, die die Liste mit unterschiedlichen Geschwindigkeiten durchlaufen.

Zum Beispiel rückt die langsame Referenz um einen Knoten vor, während die schnelle Referenz um zwei Knoten vorrückt. Wenn die verknüpfte Liste eine Schleife enthält, treffen diese Referenzen schließlich aufeinander. Wenn es andererseits keine Schleife gibt, werden entweder die langsame oder die schnelle Referenz (oder ihre nachfolgenden Referenzen) null, bevor die andere das Ende der Liste erreicht.

Hier ist eine Java-Implementierung von Floyds Algorithmus :

boolean hasLoop(Node first) {
    if (first == null) {
        return false; // List does not exist, so no loop
    }

    Node slow, fast; // Create two references.
    slow = fast = first; // Make both refer to the start of the list.

    while (true) {
        slow = slow.next; // One hop.

        if (fast.next != null) {
            fast = fast.next.next; // Two hops.
        } else {
            return false; // No loop.
        }

        if (slow == null || fast == null) {
            return false; // No loop.
        }

        if (slow == fast) {
            return true; // Loop detected.
        }
    }
}

Dieser Algorithmus benötigt eine O(1)-Raumkomplexität und läuft in O(n)-Zeit, was ihn sowohl speichereffizient als auch einigermaßen zeitaufwändig macht.