0Pricing
DSA Interview Prep · Lektion

Zykluserkennung mit Floyds Algorithmus

Erkennen Sie Zyklen mit dem Ansatz des langsamen und schnellen Zeigers, finden Sie den Einstiegspunkt des Zyklus und beweisen Sie die Korrektheit des Algorithmus mathematisch.

Zykluserkennung mit Floyds Algorithmus ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was ist ein Zyklus in einer verketteten Liste?

Ein Zyklus in einer verketteten Liste entsteht, wenn der next-Zeiger eines Knotens auf einen bereits besuchten Knoten zurückzeigt und dadurch eine Endlosschleife erzeugt. Das Durchlaufen einer solchen Liste mit einer while head-Schleife würde nie enden. Die Zykluserkennung ist ein klassisches Problem in Vorstellungsgesprächen und bildet die Grundlage für fortgeschrittenere Zeigeralgorithmen.

Der naive Ansatz speichert jeden besuchten Knoten in einer Menge und prüft, ob er bereits enthalten ist – O(n)-Zeit und O(n)-Speicher. Floyds Algorithmus löst dasselbe Problem in O(n)-Zeit und mit O(1) Speicher, was Interviewer erwarten.

Floyds Slow-Fast-Pointer-Algorithmus

Floyds Zykluserkennung (die „Schildkröte und der Hase“) verwendet zwei Zeiger: slow bewegt sich pro Schritt um eine Position weiter, fast um zwei. Wenn kein Zyklus existiert, erreicht fast zuerst None. Wenn ein Zyklus existiert, überrundet fast slow innerhalb des Zyklus schließlich und beide treffen sich am selben Knoten. Dieses Zusammentreffen beweist, dass ein Zyklus existiert.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# Build: 3 -> 2 -> 0 -> -4 -> (back to 2)
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]   # cycle: -4 -> 2

print(hasCycle(nodes[0]))  # True

Warum sich Slow und Fast immer treffen

Anschaulich gilt: Sobald beide Zeiger in den Zyklus eingetreten sind, verändert sich der Abstand zwischen ihnen pro Schritt um 1 (fast gewinnt 2 Positionen, slow 1, daher verringert sich der Abstand in jeder Runde um 1). Schließlich wird der Abstand 0 – beide befinden sich am selben Knoten. Formaler ausgedrückt: Wenn der Zyklus die Länge C hat, beträgt der maximale Abstand innerhalb des Zyklus C-1. Da sich der Abstand in jedem Schritt um 1 verringert, treffen sie sich innerhalb von C Schritten, nachdem beide in den Zyklus eingetreten sind.

Schritte bis zum Zusammentreffen insgesamt: höchstens O(n + C) = O(n), da C <= n gilt.

# Visualise convergence: simulate gap in cycle
cycle_length = 5
for start_gap in range(1, cycle_length + 1):
    gap = start_gap
    steps = 0
    while gap != 0:
        gap = (gap - 1) % cycle_length
        steps += 1
    print(f'Start gap {start_gap}: meet after {steps} step(s)')

Zyklus-Einstiegspunkt finden

Nach der Erkennung eines Zyklus kann Floyds Algorithmus auch den Eintrittsknoten finden, an dem der Zyklus beginnt. Nachdem sich slow und fast innerhalb des Zyklus getroffen haben, setzen Sie einen Zeiger auf den Kopf zurück und lassen den anderen am Treffpunkt. Bewegen Sie anschließend beide Zeiger Schritt für Schritt um jeweils eine Position weiter. Sie werden sich genau am Eintrittsknoten des Zyklus treffen. Dies funktioniert, weil der Abstand vom Kopf zum Eintritt dem Abstand vom Treffpunkt zum Eintritt (modulo der Zykluslänge) entspricht.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    # Phase 1: detect meeting point
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # no cycle
    # Phase 2: find entry
    pointer = head
    while pointer is not slow:
        pointer = pointer.next
        slow    = slow.next
    return pointer  # cycle entry node

nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]  # entry is nodes[1] (val=2)

entry = detectCycle(nodes[0])
print(entry.val)  # 2

Mathematischer Beweis für den Eintrittsknoten

Sei F = der Abstand vom Kopf zum Zykluseintritt, C = die Zykluslänge und a = der Abstand vom Eintritt zum Treffpunkt innerhalb des Zyklus. Beim Zusammentreffen ist slow F + a Schritte gelaufen; fast ist F + a + n*C Schritte gelaufen (n vollständige Runden voraus). Da fast = 2 * slow gilt: 2(F+a) = F+a+nC → F = nC - a. Daraus folgt, dass der Abstand vom Kopf zum Eintritt dem Abstand vom Treffpunkt zum Eintritt (modulo C) entspricht. Wenn Sie einen Zeiger auf den Kopf zurücksetzen und beide um jeweils 1 weiterbewegen, treffen sie sich am Eintrittsknoten.

# Verify with our example: F=1 (head to node 2), C=3 (cycle: 2->0->-4->2), a=?
# Meeting inside cycle after F+a slow steps
# Let us measure a by counting from entry to meeting point
# In practice the code handles this automatically
F = 1   # head(3) to entry(2)
C = 3   # cycle length 2->0->-4
# n=1: F = 1*C - a => a = C - F = 3 - 1 = 2
a = C - F
print(f'F={F}, C={C}, a={a}')
print(f'After meeting, {F} more steps reach entry: {F == C - a or F % C == (C - a) % C}')

Zykluslänge messen

Sobald Sie den Treffpunkt innerhalb des Zyklus kennen (Phase 1 von Floyds Algorithmus), können Sie die Zykluslänge messen: Lassen Sie einen Zeiger stehen und bewegen Sie den anderen weiter, bis beide sich erneut treffen. Die Anzahl der ausgeführten Schritte entspricht der Zykluslänge. Dies ist nützlich bei Problemen, in denen ausdrücklich nach der Zykluslänge gefragt wird.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def cycle_length(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # found meeting point
            length = 1
            fast = fast.next
            while fast is not slow:
                fast = fast.next
                length += 1
            return length
    return 0  # no cycle

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle: 3->4->5->3, length=3
print(cycle_length(nodes[0]))  # 3

Happy Number (Zykluserkennung ohne Liste)

Floyds Algorithmus ist nicht auf verkettete Listen beschränkt. LeetCode 202 „Happy Number“ fragt, ob das wiederholte Ersetzen von n durch die Summe der Quadrate seiner Ziffern schließlich 1 erreicht. Wenn die Folge in einen Zyklus eintritt, der 1 nicht enthält, läuft sie endlos weiter. Sie können dies als virtuelles Durchlaufen einer verketteten Liste modellieren, bei dem das 'next' jedes Knotens der jeweils nächste berechnete Wert ist – und anschließend Floyds Algorithmus zur Zykluserkennung anwenden.

def isHappy(n):
    def next_val(x):
        total = 0
        while x:
            x, d = divmod(x, 10)
            total += d * d
        return total

    slow, fast = n, next_val(n)
    while fast != 1 and slow != fast:
        slow = next_val(slow)
        fast = next_val(next_val(fast))
    return fast == 1

print(isHappy(19))  # True  (1->81+1=82->68->100->1)
print(isHappy(2))   # False (enters cycle)

Naive mengenbasierte Erkennung vs. Floyds Algorithmus

Der mengenbasierte Ansatz speichert jeden besuchten Knoten in einer Menge und prüft vor dem Besuch, ob er bereits enthalten ist. Er benötigt O(n)-Zeit und O(n)-Speicher. Floyds Algorithmus benötigt ebenfalls O(n)-Zeit, aber nur O(1)-Speicher – keine zusätzliche Datenstruktur. In speicherbeschränkten Umgebungen (eingebetteten Systemen, Betriebssystemkernen) ist die O(1)-Speichergrantie entscheidend. Interviewer fragen manchmal ausdrücklich nach O(1)-Speicher, nachdem Sie die Lösung mit einer Menge vorgestellt haben.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Naive O(n) space approach
def hasCycle_set(head):
    seen = set()
    while head:
        if id(head) in seen:
            return True
        seen.add(id(head))
        head = head.next
    return False

# Floyd's O(1) space approach
def hasCycle_floyd(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

print('Both implementations give the same result')

Sonderfälle bei der Zykluserkennung

Drei Sonderfälle müssen behandelt werden. Erstens: leere Liste: head is None – die Floyd-Schleifenbedingung fast and fast.next wird sofort beendet und gibt False zurück. Zweitens: einzelner Knoten ohne Zyklus: fast.next ist None, die Schleife wird beendet und gibt False zurück. Drittens: einzelner Knoten mit Zyklus: Der next-Zeiger des Knotens zeigt auf ihn selbst – slow und fast starten beide am Kopf. Nach einem Schritt bewegt sich fast zu head.next.next = head, während slow bei head.next = head steht. Daher gilt bereits im allerersten Durchlauf fast == slow.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# Edge cases
print(hasCycle(None))               # False: empty
node = ListNode(1)
print(hasCycle(node))               # False: single, no cycle
node.next = node
print(hasCycle(node))               # True: single node cycle

Zyklus in verketteter Liste II: LeetCode 142

LeetCode 142 „Linked List Cycle II“ fordert den Knoten an, an dem der Zyklus beginnt (oder None, falls kein Zyklus existiert). Dies ist die direkte Anwendung von Floyds Algorithmus in zwei Phasen. Interviewer stellen diese Aufgabe häufig als Anschlussfrage an die grundlegende Zykluserkennung. Die vollständige Lösung: Phase 1 findet den Treffpunkt innerhalb des Zyklus; Phase 2 setzt einen Zeiger auf den Kopf zurück und bewegt beide vorwärts, bis sie sich treffen – dieser Treffpunkt ist der Zykluseintritt.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def detectCycle(head):
    slow = fast = head
    # Phase 1
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None
    # Phase 2
    ptr = head
    while ptr is not slow:
        ptr  = ptr.next
        slow = slow.next
    return ptr

nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
    nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2]  # cycle entry: node with val=3
entry = detectCycle(nodes[0])
print(entry.val)  # 3

Warum Floyds Algorithmus dem Mengenansatz überlegen ist

Obwohl beide Ansätze O(n)-Zeit benötigen, unterscheidet sich der konstante Faktor in der Praxis. Der Mengenansatz muss jeden Knoten-Zeiger hashen (Hash berechnen, die Hashtabelle durchsuchen und den Zeiger speichern), während Floyds Algorithmus nur Zeigerdereferenzierungen durchführt – pro Schritt deutlich günstiger. Noch wichtiger ist die O(1)-Speichergrantie: Floyds Algorithmus kann dadurch Listen beliebiger Länge ohne das Risiko eines Speichermangels verarbeiten.

Wenn Sie diesen Speichervorteil in einem Vorstellungsgespräch von sich aus erwähnen, signalisiert das ein tiefes Verständnis algorithmischer Abwägungen, das über die reine Big-O-Notation hinausgeht.

Kurzer Test

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.

Lektionsrückblick

In dieser Lektion haben Sie gelernt: Floyds Slow-Fast-Pointer-Algorithmus erkennt Zyklen in O(n)-Zeit und mit O(1)-Speicher, Phase 2 (einen Zeiger auf den Kopf zurücksetzen und beide um 1 weiterbewegen) findet den exakten Eintrittsknoten des Zyklus und dieselbe Technik lässt sich über verkettete Listen hinaus auf jede implizite Sequenz anwenden, in der 'next' eine Funktion ist. Als Nächstes behandeln wir das Zusammenführen sortierter Listen, das Aufteilen von Listen am Mittelpunkt und das Finden des n-ten Knotens vom Ende.

Häufig gestellte Fragen

Ist die Lektion „Zykluserkennung mit Floyds Algorithmus“ kostenlos?

Ja — der vollständige Text von „Zykluserkennung mit Floyds Algorithmus“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Zykluserkennung mit Floyds Algorithmus“?

Erkennen Sie Zyklen mit dem Ansatz des langsamen und schnellen Zeigers, finden Sie den Einstiegspunkt des Zyklus und beweisen Sie die Korrektheit des Algorithmus mathematisch. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um DSA Interview Prep zu starten?

Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.

Wie lange dauert die Lektion „Zykluserkennung mit Floyds Algorithmus“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?

Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Node-Klasse und Listenerstellung
  2. Eine verkettete Liste umkehren
  3. Zykluserkennung mit Floyds Algorithmus
  4. Zusammenführen, Teilen und das n-te Element vom Ende finden
← Zurück zu DSA Interview Prep