Floyds Algorithmus: So finden Sie den Zyklusanfang in verketteten Listen

Das Entdecken von Zyklen in verketteten Listen ist eine klassische Aufgabe in technischen Vorstellungsgesprächen. Doch wie lässt sich der Startpunkt eines solchen Zyklus effizient bestimmen, ohne zusätzlichen Speicher zu verbrauchen? Die Antwort liegt in Floyds Tortoise-and-Hare-Algorithmus – einer eleganten Lösung, die mit zwei Zeigern arbeitet, die sich mit unterschiedlicher Geschwindigkeit durch die Liste bewegen.

Warum verkettete Listen Zyklen enthalten können

Verkettete Listen bestehen aus Knoten, von denen jeder einen Wert und einen Verweis auf den nächsten Knoten enthält. Unter normalen Umständen endet die Liste beim letzten Knoten mit einem null-Verweis. Doch in bestimmten Szenarien – etwa durch fehlerhafte Implementierungen oder gezielte Manipulation – kann sich ein Knoten auf einen vorherigen Knoten beziehen und so einen Zyklus erzeugen. Dieser Zyklus kann zu endlosen Schleifen führen, wenn die Liste durchlaufen wird.

Die Herausforderung besteht darin, nicht nur das Vorhandensein eines Zyklus zu erkennen, sondern auch dessen Startpunkt zu identifizieren. Dies ist besonders relevant in Anwendungen wie Speicherverwaltung oder Graphenalgorithmen, wo Zyklen zu schwerwiegenden Problemen führen können.

Der naive Ansatz: HashSet zur Speicherung besuchter Knoten

Ein naheliegender Lösungsansatz besteht darin, jeden besuchten Knoten in einer HashSet-Datenstruktur zu speichern. Während wir die Liste durchlaufen, überprüfen wir, ob der aktuelle Knoten bereits in der Menge enthalten ist.

public ListNode detectCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    while (head != null) {
        if (visited.contains(head)) {
            return head;
        }
        visited.add(head);
        head = head.next;
    }
    return null;
}

Dieser Ansatz funktioniert zuverlässig, erfordert jedoch zusätzlichen Speicher proportional zur Anzahl der Knoten – ein Nachteil, insbesondere in speicheroptimierten Umgebungen. Genau hier setzt Floyds Algorithmus an, indem er mit konstantem Speicherbedarf arbeitet.

Floyds Algorithmus: Die optimale Lösung

Floyds Tortoise-and-Hare-Algorithmus nutzt zwei Zeiger, die sich mit unterschiedlicher Geschwindigkeit durch die Liste bewegen. Der langsame Zeiger (slow) bewegt sich einen Schritt pro Iteration, während der schnelle Zeiger (fast) zwei Schritte zurücklegt. Wenn ein Zyklus existiert, werden sich die beiden Zeiger irgendwann innerhalb des Zyklus treffen.

Schritt-für-Schritt-Erklärung

1. Zykluserkennung: Bewegen Sie beide Zeiger durch die Liste, bis sie sich treffen oder das Ende der Liste erreicht wird.

1. Zurücksetzen des langsamen Zeigers: Sobald die Zeiger sich treffen, setzen Sie den langsamen Zeiger an den Anfang der Liste zurück.

1. Gleichzeitige Bewegung: Bewegen Sie beide Zeiger nun mit einer Geschwindigkeit von einem Schritt pro Iteration. Der Punkt, an dem sie sich erneut treffen, ist der Start des Zyklus.

Mathematische Begründung

Die Funktionsweise des Algorithmus lässt sich mathematisch erklären. Angenommen, die Distanz vom Listenanfang bis zum Zyklusanfang beträgt L, die Distanz vom Zyklusanfang bis zum Treffpunkt C und die verbleibende Zykluslänge R.

• Der langsame Zeiger legt die Strecke L + C zurück.
• Der schnelle Zeiger legt die Strecke L + C + n(C + R) zurück, wobei n die Anzahl der vollständigen Durchläufe durch den Zyklus beschreibt.

Da der schnelle Zeiger doppelt so schnell ist, gilt:

2(L + C) = L + C + n(C + R)
L + C = n(C + R)
L = (n - 1)(C + R) + R

Diese Gleichung zeigt, dass sich der langsame Zeiger nach Zurücksetzen an den Listenanfang und gleichzeitiger Bewegung mit dem schnellen Zeiger genau am Zyklusanfang treffen wird.

Praktische Implementierung in Java

Die folgende Implementierung zeigt, wie Floyds Algorithmus in der Praxis angewendet wird:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        // Zyklus erkennen
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // Zyklusanfang finden
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

Beispiel-Durchlauf

Betrachten wir die Liste 3 -> 2 -> 0 -> -4 mit einem Zyklus, der bei Knoten 2 beginnt. Die Zeiger bewegen sich wie folgt:

• Iteration 1: slow bewegt sich zu 2, fast zu 0.
• Iteration 2: slow bewegt sich zu 0, fast zu 2.
• Iteration 3: slow bewegt sich zu -4, fast zu -4 – die Zeiger treffen sich.

Nach Zurücksetzen des langsamen Zeigers an den Listenanfang und gleichzeitiger Bewegung treffen sich die Zeiger erneut bei Knoten 2, dem Zyklusanfang.

Komplexitätsanalyse und Anwendungsfälle

Floyds Algorithmus bietet eine optimale Lösung mit folgenden Komplexitäten:

• Zeitkomplexität: O(N) – sowohl für die Zykluserkennung als auch für die Bestimmung des Zyklusanfangs.
• Speicherkomplexität: O(1) – es werden nur zwei Zeiger benötigt, unabhängig von der Listengröße.

Typische Anwendungsfälle

Dieser Algorithmus wird in verschiedenen Szenarien eingesetzt, darunter:

• Erkennung von Zyklen in verketteten Listen.
• Lösung des Problems des „glücklichen Zahlen“ (Happy Number).
• Überprüfung auf Duplikate in sequenziellen Daten.
• Analyse von kreisförmigen Arrays.

Fazit: Ein unverzichtbares Werkzeug für Entwickler

Floyds Tortoise-and-Hare-Algorithmus ist ein Meisterwerk der Algorithmik, das mit minimalem Aufwand maximale Effizienz bietet. Seine Anwendung in Vorstellungsgesprächen unterstreicht nicht nur technisches Verständnis, sondern auch die Fähigkeit, komplexe Probleme in einfache, elegante Lösungen zu überführen.

Für Entwickler, die mit verketteten Listen oder Graphen arbeiten, ist dieses Wissen unverzichtbar. Es ermöglicht nicht nur die zuverlässige Erkennung von Zyklen, sondern auch deren effiziente Behandlung – eine Fähigkeit, die in modernen Softwareprojekten immer wichtiger wird.