Algorithmen und Datenstrukturen · Middle · Frage 25 von 75
Wie findet man die Mitte einer verketteten Liste in einem Durchlauf?
- 1Langsamer und schneller Zeiger: endet der schnelle, ist der langsame in der Mitte
- 2Die Längen-Property der Liste lesen und zu
length / 2springen - 3Die Liste umdrehen und von beiden Enden laufen, bis sie sich treffen
Antwort zeigen
Richtige Antwort: Langsamer und schneller Zeiger: endet der schnelle, ist der langsame in der Mitte
Erklärung
Eine einfach verkettete Liste kennt ihre Länge nicht, man bräuchte sonst zwei Durchläufe. Der Trick mit langsamem und schnellem Zeiger findet die Mitte in einem Durchlauf mit O(1) Speicher.