Algorithmen und Datenstrukturen · Middle · Frage 24 von 75
Wie erkennt man mit O(1) zusätzlichem Speicher einen Zyklus in einer verketteten Liste?
- 1Ein langsamer und ein schneller Zeiger: sie treffen sich nur bei einem Zyklus
- 2Die Knoten zählen und mit der Längen-Property der Liste vergleichen
- 3Jeden besuchten Knoten in einem
Setspeichern und auf Wiederholung prüfen
Antwort zeigen
Richtige Antwort: Ein langsamer und ein schneller Zeiger: sie treffen sich nur bei einem Zyklus
Erklärung
Das ist Floyds Algorithmus „Hase und Igel“. Gibt es einen Zyklus, überrundet der schnelle Zeiger irgendwann den langsamen; sonst erreicht er null. Ein Set geht auch, braucht aber O(n) Speicher.