Reverse Linked List

Q: Wie kehrt man eine verkettete Liste an Ort und Stelle um?

Durchlaufe die Liste mit zwei Zeigern: prev beginnt bei nichts und node beim Kopf. Speichere bei jedem Knoten den nächsten Knoten, setze seinen Link auf prev und bewege dann prev und node jeweils einen Schritt weiter. Wenn node das Ende erreicht, ist prev der Kopf der umgekehrten Liste.

Q: Wie hoch sind die Zeit- und Speicherkomplexität beim Umkehren einer verketteten Liste?

Die iterative Version besucht jeden Knoten einmal, O(n) Zeit, und behält drei Zeiger bei, O(1) zusätzlicher Speicherplatz. Die Reihenfolge zuerst in ein Array zu kopieren, benötigt ebenfalls O(n) Zeit, aber O(n) zusätzlichen Speicherplatz. Eine rekursive Version verwendet O(n) Speicherplatz für den Aufrufstapel.

LeichtVerkettete Liste

+10

Du erhältst eine einfach verkettete Liste, die im Array next gespeichert ist: Knoten i verweist auf Knoten next[i], -1 beendet die Liste, und der Kopf ist Knoten 0. Die Knoten sind nicht in Listenreihenfolge gespeichert, folge also den Verweisen.

Kehre die Liste um, indem du jeden Verweis umdrehst, sodass der bisherige letzte Knoten zum Kopf wird und Knoten 0 zum letzten Knoten wird, der auf -1 verweist. Gib das aktualisierte next-Array zurück, das dieselbe Länge wie die Eingabe hat.

Funktion

reverseList(next: integer-array) → integer-array

nextinteger-array: der Index des Knotens, auf den jeder Knoten verweist, oder -1 für den letzten Knoten
Gibt zurückinteger-array: das nächste Array der umgekehrten Liste

Einschränkungen

1 ≤ next.length ≤ 5000
Jedes next[i] ist -1 oder ein Knotenindex von 0 bis next.length-1.
Ausgehend vom Knoten 0 besucht die Liste jeden Knoten genau einmal und erreicht dann -1. Es gibt keinen Zyklus.

Beispiele

Eingabe: next = [1, 2, 3, -1]
Ausgabe: [-1, 0, 1, 2]
Erklärung: Die Liste lautet 0 → 1 → 2 → 3. Umgekehrt ist sie 3 → 2 → 1 → 0, also verweist Knoten 3 auf 2, Knoten 2 auf 1, Knoten 1 auf 0 und Knoten 0 auf -1.

Eingabe: next = [2, -1, 3, 1]
Ausgabe: [-1, 3, 0, 2]
Erklärung: Die Liste lautet 0 → 2 → 3 → 1, und umgekehrt lautet sie 1 → 3 → 2 → 0. Wenn du jeden neuen Link am Index seines Knotens einträgst, erhältst du [-1, 3, 0, 2]. Würdest du das Array selbst umkehren, erhieltest du [1, 3, -1, 2], was nicht dasselbe ist.

Eingabe: next = [-1]
Ausgabe: [-1]
Erklärung: Ein einzelner Knoten ist seine eigene Umkehrung. Er bleibt Kopf und Ende und verweist weiterhin auf -1.

+11 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du nur den Teil der Liste zwischen Position left und Position right umkehren und die Knoten davor und danach an ihrer Stelle belassen?

Tipps

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

0 von 3 geöffnet

Lösung

Beim Umkehren einer Liste wird kein Knoten verschoben; stattdessen wird jede Verknüpfung umgedreht. Der Haken dabei ist, dass die Verknüpfung eines Knotens der einzige Weg ist, den Rest der Liste zu erreichen. Sobald du sie überschreibst, geht alles dahinter verloren. Du kannst das Problem vermeiden, indem du zuerst die Reihenfolge notierst, oder du gehst die Liste einmal mit drei Zeigern durch, die den Weg nach vorn sichern, bevor jede Verknüpfung umgedreht wird.

Schreibe die Reihenfolge auf und verknüpfe sie dann neu

Idee

In diesem Problem ist ein Zeiger ein Knotenindex, und vorwärtszugehen bedeutet node = next[node]. Gehe von Knoten 0 aus weiter, bis du -1 erreichst, und notiere jeden Knoten, an dem du vorbeikommst. Im zweiten Beispiel ergibt das die Reihenfolge [0, 2, 3, 1].

In der umgekehrten Liste verweist jeder Knoten auf den Knoten, der in dieser Reihenfolge vor ihm kam: 1 verweist auf 3, 3 auf 2, 2 auf 0. Vor dem ersten Knoten der Reihenfolge, dem alten Kopf, kommt nichts, also verweist er auf -1. Fülle ein neues Array mit diesen Verweisen und gib es zurück.

Da jeder Verweis in ein neues Array geschrieben wird, wird nichts überschrieben, solange du es noch benötigst. Dadurch ist es bei dieser Variante schwierig, einen Fehler zu machen. Sie benötigt O(n) Zeit und O(n) zusätzlichen Speicherplatz für die Reihenfolge und das neue Array.

Algorithmus

Gehe von Knoten 0 zu -1 und füge jeden Knoten zu order hinzu.
Erstelle ein neues Array derselben Länge.
Setze den Eintrag von order[0] auf -1.
Setze für jedes k ≥ 1 den Eintrag von order[k] auf order[k-1].
Gib das neue Array zurück.

def reverseList(next):
    order = []
    node = 0
    while node != -1:
        order.append(node)
        node = next[node]
    reversed_next = [0] * len(next)
    reversed_next[order[0]] = -1  # the old head ends the new list
    for k in range(1, len(order)):
        reversed_next[order[k]] = order[k - 1]
    return reversed_next

Die Verknüpfungen in einem Durchgang umkehren

Idee

Du kannst jede Verknüpfung umdrehen, sobald du ihren Knoten erreichst, wenn du dich an den Knoten erinnerst, von dem du gekommen bist. Behalte prev, den Knoten hinter dir, und beginne mit -1, da der alte Kopf zum letzten Knoten wird. Bei node zeigt die Verknüpfung next[node] nach vorne; setze sie auf prev, damit sie rückwärts zeigt.

Durch diese Zuweisung verlierst du deine einzige Möglichkeit, vorwärtszugehen. Speichere den Wert daher zuerst in einer dritten Variablen: after = next[node]. Drehe dann die Verknüpfung um und rücke beide Zeiger um einen Schritt weiter: prev = node, node = after. Zu jedem Zeitpunkt bilden die Knoten hinter dir eine umgekehrte Liste mit prev als Kopf, während die Knoten vor dir den unveränderten Rest bilden, der bei node beginnt. Wenn node -1 erreicht, wurden alle Verknüpfungen umgedreht und prev ist der neue Kopf.

Im zweiten Beispiel durchlaufen die Zeiger die Knoten 0, 2, 3, 1 und schreiben next[0] = -1, next[2] = 0, next[3] = 2 und next[1] = 3. Jeder Knoten wird genau einmal besucht: Laufzeit O(n), und der einzige Speicherbedarf sind drei Ganzzahlen: O(1).

Algorithmus

Setze prev = -1 und node = 0.
Solange node nicht -1 ist, speichere after = next[node].
Setze next[node] = prev.
Fahre fort: prev = node, dann node = after.
Gib next zurück.

def reverseList(next):
    prev = -1  # the node behind the current one; the old head will point to -1
    node = 0
    while node != -1:
        after = next[node]  # save the rest of the list before cutting the link
        next[node] = prev
        prev = node
        node = after
    return next

Stolperfallen und Grenzfälle

Fast jeder Fehler hier betrifft die Reihenfolge der drei Zuweisungen oder die beiden Enden der Liste.

next[node] überschreiben, bevor der Wert gespeichert wird. Nach next[node] = prev ist die alte Vorwärtsverknüpfung verloren, und der Durchlauf springt rückwärts statt zum nächsten Knoten weiterzugehen.
prev mit etwas anderem als -1 beginnen lassen. Der alte Kopf muss die neue Liste beenden. Beginnt man mit 0, verweist Knoten 0 auf sich selbst.
Das Array statt der Verknüpfungen umkehren. Die Knoten sind nicht in Listenreihenfolge gespeichert, und die Antwort behält jeden Knoten an seinem eigenen Index; nur die Werte ändern sich. Das Umkehren von [2, -1, 3, 1] ergibt [1, 3, -1, 2], nicht [-1, 3, 0, 2].
Mit einer Schleife über next[node] != -1 einen Knoten zu früh aufhören. Auch die Verknüpfung des letzten Knotens muss umgekehrt werden. Daher muss die Schleife laufen, solange node != -1 gilt.
Eine lange Liste rekursiv umkehren. Eine Liste mit 5000 Knoten erfordert 5000 verschachtelte Aufrufe und überschreitet damit Pythons Limit von 1000.
Den Versatz in Lua und R vergessen, wo Arrays bei 1 beginnen. Die Knotenindizes bleiben bei 0-basiert, und lies next[node + 1]. Ruby und R reservieren das Wort next, daher nennen ihre Starter den Parameter next_.

Häufige Fragen4

Wie kehrt man eine verkettete Liste an Ort und Stelle um?

Durchlaufe die Liste mit zwei Zeigern: prev beginnt bei nichts und node beim Kopf. Speichere bei jedem Knoten den nächsten Knoten, setze seinen Link auf prev und bewege dann prev und node jeweils einen Schritt weiter. Wenn node das Ende erreicht, ist prev der Kopf der umgekehrten Liste.

Wie hoch sind die Zeit- und Speicherkomplexität beim Umkehren einer verketteten Liste?

Die iterative Version besucht jeden Knoten einmal, O(n) Zeit, und behält drei Zeiger bei, O(1) zusätzlicher Speicherplatz. Die Reihenfolge zuerst in ein Array zu kopieren, benötigt ebenfalls O(n) Zeit, aber O(n) zusätzlichen Speicherplatz. Eine rekursive Version verwendet O(n) Speicherplatz für den Aufrufstapel.

Kannst du eine verkettete Liste rekursiv umkehren?

Ja. Kehre alles nach dem Kopf um, dann zeige mit dem alten Nachfolger des Kopfes zurück auf den Kopf und setze den Verweis des Kopfes auf nichts. Das liest sich gut, aber es erfolgt ein verschachtelter Aufruf pro Knoten, sodass bei einer langen Liste der Aufrufstapel überlaufen kann. Python stoppt standardmäßig nach 1000 Aufrufen; eine Liste mit 5000 Knoten überschreitet diesen Wert.

Warum benötigt das Umkehren einer verketteten Liste drei Zeiger?

Um die Verknüpfung eines Knotens umzudrehen, brauchst du den Knoten selbst und den Knoten davor, also zwei Zeiger. Der dritte hält den Knoten danach fest, weil beim Umdrehen der Verknüpfung die einzige Referenz auf den Rest der Liste gelöscht wird. Ohne ihn kann die Durchlaufung nicht fortgesetzt werden.

Python

def reverseList(next):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

next = [1, 2, 3, -1]

Erwartet

[-1, 0, 1, 2]