Linked List Cycle

Q: Wie hoch sind die Zeit- und Speicherkomplexität von Linked List Cycle?

Beide Ansätze benötigen O(n) Zeit, da jeder Knoten eine begrenzte Anzahl von Malen durchlaufen wird. Das Markieren besuchter Knoten benötigt O(n) zusätzlichen Speicher. Floyds schnelle und langsame Zeiger benötigen O(1) : zwei Knotennummern.

Q: Warum kann der schnelle Zeiger nicht über den langsamen Zeiger springen?

Innerhalb des Zyklus bewegt sich fast pro Runde um zwei Knoten und slow um einen, sodass die Strecke, die fast noch zurücklegen muss, um slow zu erreichen, genau um eins abnimmt. Eine Strecke, die pro Runde um eins abnimmt, verläuft über 3, 2, 1, 0 und kann nicht unter null sinken, sodass sich die beiden Zeiger an einem Knoten treffen.

LeichtSchneller und langsamer Zeiger Verkettete Liste

+10

Eine verkettete Liste ist im Array next gespeichert: Der Knoten i verweist auf den Knoten next[i], und -1 bedeutet, dass die Liste dort endet. Der Kopf ist Knoten 0. Folge den Verweisen vom Kopf aus und gib true zurück, wenn du zu einem Knoten zurückkehrst, den du bereits besucht hast, oder false, wenn du das Ende erreichst. Knoten, die beim Durchlaufen nie erreicht werden, zählen nicht, selbst wenn sie in einer Schleife aufeinander verweisen.

Funktion

hasCycle(next: integer-array) → boolean

nextinteger-array: der Verweis jedes Knotens: next[i] ist der Knoten nach Knoten i oder -1
Gibt zurückboolean: true, wenn der Pfad von Knoten 0 aus einen Knoten erneut besucht, false, wenn er -1 erreicht

Einschränkungen

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
Mehrere Knoten können mit demselben Knoten verknüpft sein, und einige Knoten sind möglicherweise vom Kopf aus nicht erreichbar.

Beispiele

Eingabe: next = [1, 2, 3, 1]
Ausgabe: true
Erklärung: Der Durchlauf geht über 0, 1, 2, 3 und dann zurück zu 1. Knoten 1 wird zweimal besucht, daher enthält die Liste einen Zyklus durch die Knoten 1, 2 und 3.

Eingabe: next = [2, -1, 1]
Ausgabe: false
Erklärung: Der Pfad geht von 0 zu 2, dann zu 1 und erreicht anschließend -1: drei verschiedene Knoten und dann das Ende, also gibt es keinen Zyklus.

Eingabe: next = [-1, 2, 1]
Ausgabe: false
Erklärung: Knoten 0 verweist auf -1, daher ist die Liste einen Knoten lang. Die Knoten 1 und 2 verweisen in einer Schleife aufeinander, aber der Durchlauf ab dem Kopf erreicht sie nie.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du auch den Knoten finden, an dem der Zyklus beginnt, weiterhin mit O(1) zusätzlichem Speicher?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Eine Liste ohne Zyklus erreicht innerhalb von n Verbindungen -1, aber eine Liste mit einem Zyklus endet nie, daher kannst du nicht auf das Ende warten. Du brauchst eine Möglichkeit zu erkennen, dass der Durchlauf im Kreis geht. Wenn du dir jeden besuchten Knoten merkst, benötigst du dafür O(n) Speicher. Floyds schnelle und langsame Zeiger kommen mit zwei Ganzzahlen aus, denn ein Zeiger, der sich doppelt so schnell bewegt, muss den langsamen innerhalb einer Schleife einholen.

Markiere die Knoten, die du besuchst

Idee

Gehe von Knoten 0 aus los und markiere jeden Knoten, wenn du ihn verlässt. Wenn du bei einem bereits markierten Knoten ankommst, ist der Weg zu ihm zurückgekehrt und wiederholt sich von dort an für immer: Das ist ein Zyklus. In Beispiel 1 markierst du 0, 1, 2 und 3, und die Verbindung von Knoten 3 führt zu Knoten 1, der bereits markiert ist.

Die Knoten sind von 0 bis n-1 nummeriert, daher dient ein boolesches Array der Länge n als Menge der besuchten Knoten. Bei einer verketteten Liste aus Objekten würdest du stattdessen die Knotenreferenzen in einer Hashtabelle speichern; die Idee ist dieselbe.

Jeder Knoten wird höchstens einmal markiert, und der Weg endet bei der ersten Wiederholung oder bei -1. Daher dauert er höchstens n Schritte: O(n) Zeit und O(n) Speicher für die Markierungen.

Algorithmus

Erstelle ein boolesches Array visited der Länge n, dessen Elemente alle false sind.
Setze node = 0.
Solange node nicht -1 ist, gib true zurück, wenn visited[node] bereits true ist.
Setze andernfalls visited[node] und gehe zu next[node].
Wenn der Durchlauf -1 erreicht, gib false zurück.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

Schnelle und langsame Zeiger (Floyds Zykluserkennung)

Idee

Setze zwei Zeiger am Anfang ein. slow folgt pro Runde einem Link und fast folgt zwei. Wenn die Liste endet, erreicht fast zuerst -1 und du gibst false zurück. Gibt es einen Zyklus, tritt fast zuerst in ihn ein und dreht weiter seine Runden, bis auch slow ankommt.

Sobald beide im Zyklus sind, gewinnt fast pro Runde genau einen Knoten gegenüber slow. Die Entfernung, die fast noch zurücklegen muss, um slow zu erreichen, verringert sich pro Runde um eins, erreicht also null, und die Zeiger landen auf demselben Knoten. Da fast jeweils nur einen Knoten gewinnt, kann er nie über slow hinwegspringen.

In Beispiel 1 steht slow nach einer Runde auf Knoten 1 und fast auf Knoten 2. Nach zwei Runden steht slow auf 2 und fast ist über 3 und 1 gelaufen. Nach drei Runden stehen beide auf Knoten 3, also lautet die Antwort true.

slow benötigt höchstens n Runden, um in den Zyklus einzutreten. Sobald es sich darin befindet, treffen sie sich, bevor es eine Runde beendet hat; die Laufzeit beträgt daher O(n). Der einzige Speicherbedarf sind zwei Knotennummern.

Algorithmus

Setze slow = 0 und fast = 0.
Solange fast nicht -1 ist und next[fast] nicht -1 ist, bewege slow um eine Verknüpfung und fast um zwei Verknüpfungen weiter.
Gib nach jeder Bewegung true zurück, wenn sie sich auf demselben Knoten befinden.
Wenn die Schleife endet, hat fast das Ende gefunden: Gib false zurück.

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

Stolperfallen und Grenzfälle

Die Fehler hier betreffen das Ende der Liste und die Frage, welche Knoten zählen.

fast zwei Verknüpfungen weiterbewegen, ohne beide zu überprüfen. fast und next[fast] müssen beide echte Knoten sein, bevor du next[next[fast]] liest; andernfalls liest du next[-1], was in den meisten Sprachen zu einem Absturz führt und in Python stillschweigend das letzte Element zurückgibt.
Die Zeiger vergleichen, bevor du sie weiterbewegst. Beide starten bei Knoten 0, daher meldet eine Prüfung am Anfang der Schleife in jeder Liste einen Zyklus.
Das gesamte Array statt des Pfads betrachten. In [-1, 2, 1] bilden die Knoten 1 und 2 eine Schleife, aber der Pfad ab dem Kopf endet sofort, daher lautet die Antwort false. Zu prüfen, ob sich ein Wert in next wiederholt, ist ebenfalls falsch: In [4, 4, 4, 4, -1] zeigen mehrere Knoten auf Knoten 4, und es gibt keinen Zyklus.
Annehmen, dass ein Zyklus zum Kopf zurückführen muss. In [1, 2, 3, 4, 4] zeigt der letzte Knoten auf sich selbst, und in [0] tut der Kopf das.

Häufige Fragen4

Wie funktioniert Floyds Zykluserkennung?

Zwei Zeiger starten am Kopf: Einer bewegt sich pro Schritt um einen Knoten weiter, der andere um zwei. Ohne Zyklus erreicht der schnelle das Ende. Mit einem Zyklus landen beide darin, der schnelle holt pro Schritt einen Knoten auf, und sie treffen sich am selben Knoten.

Wie hoch sind die Zeit- und Speicherkomplexität von Linked List Cycle?

Beide Ansätze benötigen O(n) Zeit, da jeder Knoten eine begrenzte Anzahl von Malen durchlaufen wird. Das Markieren besuchter Knoten benötigt O(n) zusätzlichen Speicher. Floyds schnelle und langsame Zeiger benötigen O(1): zwei Knotennummern.

Warum kann der schnelle Zeiger nicht über den langsamen Zeiger springen?

Innerhalb des Zyklus bewegt sich fast pro Runde um zwei Knoten und slow um einen, sodass die Strecke, die fast noch zurücklegen muss, um slow zu erreichen, genau um eins abnimmt. Eine Strecke, die pro Runde um eins abnimmt, verläuft über 3, 2, 1, 0 und kann nicht unter null sinken, sodass sich die beiden Zeiger an einem Knoten treffen.

Kannst du den Zyklus durch Zählen der Schritte erkennen?

In dieser Array-Darstellung: ja. Eine Liste ohne Zyklus erreicht innerhalb von n Verknüpfungen -1. Wenn man also n Verknüpfungen durchläuft, ohne das Ende zu erreichen, ist damit ein Zyklus nachgewiesen – bei einem Speicherbedarf von O(1). Dafür muss die Anzahl der Knoten bekannt sein, die eine aus Zeigern bestehende Liste nicht angibt. Sie vorher zu zählen, kommt bei einem Zyklus nie zum Ende. Floyds Methode benötigt keine Zählung.

Python

def hasCycle(next):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

next = [1, 2, 3, 1]

Erwartet

true