Middle of the Linked List
Du erhältst eine einfach verkettete Liste, die in zwei Arrays gleicher Länge gespeichert ist. Der Knoten i enthält den Wert values[i] und ist mit dem Knoten next[i] verknüpft. -1 beendet die Liste, und der Kopf ist Knoten 0. Die Knoten sind nicht in der Reihenfolge der Liste gespeichert, folge also den Verknüpfungen.
Gib den Wert des mittleren Knotens zurück. Hat die Liste eine gerade Anzahl von Knoten, gibt es zwei mittlere Knoten; gib den Wert des zweiten zurück.
Funktion
- valuesinteger-array
- der von jedem Knoten gespeicherte Wert
- nextinteger-array
- der Index des Knotens, auf den jeder Knoten verweist, oder -1 für den letzten Knoten
- Gibt zurückinteger
- der Wert des mittleren Knotens, des zweiten mittleren Knotens, wenn die Länge gerade ist
Einschränkungen
1 ≤ n ≤ 5000, wobeindie Länge vonvaluesundnextist.-104 ≤ values[i] ≤ 104- Jedes
next[i]ist-1oder ein Knotenindex von0bisn-1. - Beginnend bei Knoten
0besucht die Liste jeden Knoten genau einmal und erreicht dann-1. Es gibt keinen Zyklus.
Beispiele
- Eingabe
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- Ausgabe
- 5
- Erklärung
- Wenn man den Verknüpfungen von Knoten
0folgt, erhält man die Knoten0, 3, 4, 2, 1; die Liste lautet also4, 7, 5, 2, 9. Der dritte der fünf Knoten ist Knoten4, dessen Wert5ist. Der mittlere Eintrag des Arrays selbst,values[2] = 2, ist ein anderer Knoten.
- Eingabe
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- Ausgabe
- 40
- Erklärung
- Hier sind die Knoten der Reihe nach gespeichert. Bei sechs Knoten gibt es zwei mittlere,
30und40, und der zweite gewinnt.
- Eingabe
- values = [8]next = [-1]
- Ausgabe
- 8
- Erklärung
- Eine Liste mit einem Knoten ist ihr eigenes mittleres Element.
+13 versteckte Tests beim Einreichen
Weiterführende Frage
Kannst du den Knoten zurückgeben, der sich ein Drittel des Weges durch die Liste befindet, und zwar in einem einzigen Durchlauf? Wie schnell würde sich jeder Zeiger bewegen, und wo würdest du anhalten?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Du kennst die Länge der Liste erst, wenn du ihr Ende erreichst. Was wäre, wenn zwei Läufer am Anfang starten und einer von ihnen sich doppelt so schnell bewegt wie der andere?
Wenn der schnellere Läufer das Ende erreicht hat, hat der langsamere die Hälfte der Strecke zurückgelegt und steht somit auf dem mittleren Knoten. Es bleibt nur noch die Frage, wann man anhalten muss, damit man bei einer geraden Länge auf dem zweiten mittleren Knoten landet.
Starte
slowundfastbei Knoten0. Solangefastnicht-1ist undnext[fast]nicht-1ist, bewegeslowum eine Verbindung undfastum zwei Verbindungen weiter. Gib dannvalues[slow]zurück.
Lösung
In einem Array liegt die Mitte am Index n / 2. Eine verkettete Liste hat keinen Index: Du erfährst erst, wie lang sie ist, wenn du bis zum Ende gehst, und dann bist du bereits an der Mitte vorbeigekommen. Du kannst die Liste in ein Array kopieren oder zuerst zählen und sie dann erneut durchlaufen. Die elegante Lösung lässt zwei Zeiger mit unterschiedlichen Geschwindigkeiten durch die Liste laufen, sodass der langsame in der Mitte ist, wenn dem schnellen die Liste ausgeht.
Kopiere die Werte in ein Array
Idee
In diesem Problem ist ein Zeiger ein Knotenindex. Zum nächsten Knoten gelangst du mit node = next[node], und wenn du -1 erreichst, bist du am Ende angekommen. Im ersten Beispiel verläuft der Weg von Knoten 0 über 0 → 3 → 4 → 2 → 1 → -1.
Das Problem mit einer Liste ist, dass du nicht direkt zu einer Position springen kannst. Verwandle sie also in etwas, mit dem das möglich ist: Durchlaufe die Liste einmal und füge jeden Wert, an dem du vorbeikommst, einem neuen Array hinzu. Dieses Array enthält die Werte in der Listenreihenfolge: [4, 7, 5, 2, 9] im ersten Beispiel. Seine Mitte liegt am Index length / 2, wobei ganzzahlig dividiert wird.
Bei einer geraden Länge liefert dieser Index von selbst die zweite Mitte: Bei sechs Werten ergibt sich Index 3, also der vierte Wert, der im zweiten Beispiel 40 ist. Der Durchlauf benötigt O(n) Zeit, und die Kopie braucht zusätzlich O(n) Speicher, den die nächsten beiden Ansätze vermeiden.
Algorithmus
- Beginne mit einem leeren Array und
node = 0. - Solange
nodenicht-1ist, fügevalues[node]hinzu und gehe zunext[node]. - Gib den Eintrag am Index
length / 2zurück, abgerundet.
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]Zähle und gehe dann die Hälfte des Weges
Idee
Du brauchst nicht die ganze Kopie, sondern nur die Länge. Gehe die Liste einmal durch und zähle die Knoten. Beginne dann erneut am Anfang und gehe length / 2 Schritte, abgerundet. Der Knoten, bei dem du anhältst, ist der mittlere.
Warum so viele Schritte: Nach k Schritten stehst du auf dem Knoten an Position k, wobei der Anfang als Position 0 gezählt wird. Die Mitte einer Liste mit 5 Elementen liegt an Position 2, und die zweite Mitte einer Liste mit 6 Elementen liegt an Position 3 – beides entspricht length / 2. Im ersten Beispiel zählst du 5, gehst zwei Schritte 0 → 3 → 4 und liest values[4] = 5.
Der Speicherbedarf beträgt jetzt O(1). Dafür musst du die Liste ein zweites Mal zur Hälfte durchlaufen. Insgesamt sind es 1.5n Schritte, was weiterhin O(n) entspricht.
Algorithmus
- Gehe von Knoten
0bis-1und zähle die Knoten. - Gehe zurück zu Knoten
0. - Führe
node = next[node]genaucount / 2-mal aus, abgerundet. - Gib
values[node]zurück.
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]Schnelle und langsame Zeiger
Idee
Setze zwei Zeiger auf den Kopf. In jeder Runde bewegt sich slow um einen Knoten und fast um zwei. Nach k Runden steht slow an Position k und fast an Position 2k, daher hat slow immer die Hälfte der von fast zurückgelegten Strecke zurückgelegt. Wenn fast das Ende erreicht, befindet sich slow in der Mitte, und du musstest die Länge nie kennen.
Die Abbruchregel entscheidet, welche Mitte du erhältst. Fahre fort, solange fast ein echter Knoten ist und danach noch ein Knoten kommt: fast != -1 und next[fast] != -1. Bei einer ungeraden Länge stoppt fast beim letzten Knoten. Bei einer geraden Länge tritt fast über das Ende hinaus und wird zu -1, wodurch slow einen Schritt weiter auf die zweite Mitte gelangt. Im zweiten Beispiel bewegt sich slow über 0, 1, 2, 3, während fast sich über 0, 2, 4, -1 bewegt, und values[3] ist 40.
Im ersten Beispiel besucht slow die Knoten 0, 3, 4, während fast die Knoten 0, 4, 1 besucht; Knoten 1 ist der letzte, daher stoppt die Schleife, wenn slow auf Knoten 4 steht, und die Antwort ist 5. Fast macht etwa n Schritte und slow n / 2 – in einem einzigen Durchlauf und mit zwei Integern Speicher.
Algorithmus
- Setze
slow = 0undfast = 0. - Solange
fast != -1undnext[fast] != -1gilt, setzeslow = next[slow]undfast = next[next[fast]]. - Gib
values[slow]zurück.
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
Stolperfallen und Grenzfälle
Die Schleife ist kurz, daher stecken die Fehler darin, wo sie beginnt, wo sie endet und was sie zurückgibt.
values[n / 2]zurückgeben. Die Knoten sind nicht in der Reihenfolge der Liste gespeichert, daher ist der mittlere Eintrag des Arrays normalerweise ein anderer Knoten. Im ersten Beispiel ergibt das2statt5.- Bei gerader Länge den ersten mittleren Knoten erhalten. Eine Schleife, die läuft, solange sowohl
next[fast]als auchnext[next[fast]]gültig sind, stoppt eine Runde zu früh und gibt im zweiten Beispiel30statt40zurück. next[fast]prüfen, bevorfast != -1geprüft wird. Bei gerader Länge wirdfastzu-1, und das Lesen vonnext[-1]führt in den meisten Sprachen zu einem Absturz. In Python wird stattdessen stillschweigend der letzte Eintrag gelesen, was noch schlimmer ist.- Beim Zählansatz
count / 2 - 1Schritte gehen oder aufrunden. Zähle den Kopf als Position0und gehe genaucount / 2Schritte, abgerundet. - Den Knotenindex statt seines Werts zurückgeben.
- Den Offset in Lua und R vergessen, wo Arrays bei 1 beginnen. Behalte Knotenindizes bei 0 bei und lies
next[node + 1]. Ruby und R reservieren das Wortnext, daher nennen ihre Startvorlagen den Parameternext_.
Häufige Fragen4
Warum finden schnelle und langsame Zeiger die Mitte einer verketteten Liste?
Beide starten am Kopf, und in jeder Runde bewegt sich der schnelle Zeiger um zwei Knoten, während sich der langsame um einen bewegt. Nach k Runden befindet sich der schnelle Zeiger an Position 2k und der langsame an Position k, also genau auf der halben Strecke. Wenn der schnelle Zeiger das Ende der Liste erreicht, befindet sich der langsame in ihrer Mitte.
Wie hoch sind die Zeit- und Platzkomplexität beim Finden der Mitte einer verketteten Liste?
Alle drei Ansätze benötigen O(n) Zeit, da sich die Mitte nicht finden lässt, ohne etwa die Hälfte der Liste oder mehr zu durchlaufen. Das Kopieren der Werte benötigt zusätzlich O(n) Speicher. Das vorherige Zählen sowie die schnellen und langsamen Zeiger benötigen beide O(1); die Zeiger brauchen nur einen Durchlauf.
Wie gibst du den ersten mittleren Knoten statt des zweiten zurück?
Ändere die Abbruchbedingung so, dass der schnelle Zeiger eine Runde früher stoppt: Schleife, solange next[fast] != -1 und next[next[fast]] != -1 gelten. Bei sechs Knoten stoppt der langsame Zeiger dann an Position 2 statt 3. Beim Zählansatz gehst du statt count / 2 Schritte (count - 1) / 2.
Wo wird die Technik mit schnellem und langsamem Zeiger noch verwendet?
Dieselben beiden Geschwindigkeiten erkennen einen Zyklus in einer verketteten Liste: In einer Schleife überholt der schnelle Zeiger den langsamen und beide treffen sich. Sie finden auch heraus, wo ein Zyklus beginnt, und teilen eine Liste für Merge-Sort oder zur Prüfung, ob sich eine Liste in beide Richtungen gleich liest, in zwei Hälften.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def middleNode(values, next):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
Erwartet
5