Remove Nth Node From End of List
Du erhältst eine einfach verkettete Liste, die in zwei Arrays gleicher Länge gespeichert ist. Knoten i enthält den Wert values[i] und verweist auf den Knoten next[i]; -1 beendet die Liste, und der Kopf ist Knoten 0. Die Knoten sind nicht in Listenreihenfolge gespeichert, folge also den Verweisen.
Entferne den n-ten Knoten, vom Ende der Liste aus gezählt, wobei der letzte Knoten der 1. vom Ende ist. Gib die Werte der verbleibenden Knoten in Listenreihenfolge zurück.
Funktion
- valuesinteger-array
- der von jedem Knoten gehaltene Wert
- nextinteger-array
- der Index des Knotens, auf den jeder Knoten verweist, oder -1 für den letzten Knoten
- ninteger
- welcher Knoten entfernt werden soll, vom Ende aus gezählt, wobei 1 der letzte Knoten ist
- Gibt zurückinteger-array
- die verbleibenden Werte in Listenreihenfolge, leer, wenn der einzige Knoten entfernt wird
Einschränkungen
1 ≤ L ≤ 5000, wobeiLdie Länge vonvaluesund vonnextist.-100 ≤ values[i] ≤ 1001 ≤ n ≤ L- Jedes
next[i]ist-1oder ein Knotenindex von0bisL-1. - Beginnend beim Knoten
0besucht die Liste jeden Knoten genau einmal und erreicht dann-1. Es gibt keinen Zyklus.
Beispiele
- Eingabe
- values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
- Ausgabe
- [5, 2, 6, 7]
- Erklärung
- Wenn man den Verknüpfungen ab Knoten
0folgt, besucht man die Knoten0, 2, 4, 1, 3, sodass die Liste5, 2, 6, 9, 7lautet. Der zweitletzte Knoten ist Knoten1mit dem Wert9; ohne ihn lautet die Liste5, 2, 6, 7. Der Array-Eintragvalues[5-2] = 7ist der letzte Knoten, nicht der zu entfernende.
- Eingabe
- values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
- Ausgabe
- [20, 30, 40]
- Erklärung
- Vier Knoten und
n = 4: Der vierte Knoten vom Ende aus ist der Kopf. Die Liste beginnt nun bei Knoten1und lautet20, 30, 40.
- Eingabe
- values = [42]next = [-1]n = 1
- Ausgabe
- []
- Erklärung
- Der einzige Knoten ist sowohl der Kopf als auch der letzte Knoten. Wenn du ihn entfernst, bleibt eine leere Liste übrig, also lautet die Antwort
[].
+14 versteckte Tests beim Einreichen
Weiterführende Frage
Kannst du den Knoten in einem einzigen Durchlauf finden und entfernen, ohne vorher die Länge zu zählen?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Eine Liste lässt sich nur vorwärts durchlaufen, und der Knoten wird durch seinen Abstand zum Ende definiert. Wenn du die Länge
Lkennen würdest, an welcher Position vom Anfang aus würde er sich befinden? Und den Link welches Knotens musst du ändern, um ihn herauszunehmen?Du kannst den Abstand zum Ende ohne die Länge messen. Setze einen Zeiger
nKnoten vor den anderen und bewege beide gemeinsam. Wenn der führende Zeiger auf dem letzten Knoten steht, steht der nachfolgende direkt vor dem zu entfernenden Knoten.Bewege
fastn-mal vorwärts. Wenn es jetzt-1ist, ist der Kopf der zu entfernende Knoten, also beginnt die Liste beinext[0]. Andernfalls bewegeslowundfastgemeinsam weiter, solangenext[fast] != -1, und setze dannnext[slow] = next[next[slow]]. Durchlaufe die Liste vom Kopf aus und sammle die Werte.
Lösung
Das Ziel wird durch seinen Abstand vom Ende definiert, aber in einer einfach verketteten Liste kannst du nur vorwärts gehen, und du erfährst erst, wo das Ende ist, wenn du es erreichst. Um einen Knoten zu entfernen, musst du außerdem auf dem Knoten davor stehen, denn dessen Verknüpfung wird geändert. Du kannst die Liste in ein Array kopieren oder sie zählen und erneut durchlaufen. Die klassische Lösung hält zwei Zeiger im Abstand von n Verknüpfungen zueinander, sodass der hintere Zeiger direkt vor dem Ziel steht, wenn der vordere den letzten Knoten erreicht. Unten bezeichnet L die Anzahl der Knoten.
Kopiere die Werte in ein Array
Idee
In diesem Problem ist ein Zeiger ein Knotenindex. Vorwärtsgehen bedeutet node = next[node], und wenn du -1 erreichst, bist du über das Ende hinausgelaufen. Im ersten Beispiel führt der Weg von Knoten 0 über 0 → 2 → 4 → 1 → 3 → -1.
Vom Ende aus zu zählen ist nur deshalb schwierig, weil eine Liste keine Positionen hat. Also gib ihr Positionen: Gehe sie einmal durch und füge jeden Wert an ein Array an. Für das erste Beispiel lautet dieses Array [5, 2, 6, 9, 7]. In einem Array mit L Werten steht der letzte an Index L-1, also steht der n-te Wert vom Ende an Index L-n. Hier ist das 5-2 = 3, die 9. Lösche ihn und gib [5, 2, 6, 7] zurück.
Das ist korrekt und läuft in O(L) Zeit, aber es kopiert die gesamte Liste und verändert keine Verknüpfung. Ziel des Problems ist es, die Liste selbst mit O(1) zusätzlichem Speicher zu bearbeiten, wie es die beiden folgenden Ansätze tun.
Algorithmus
- Beginne mit einem leeren Array und
node = 0. - Solange
nodenicht-1ist, fügevalues[node]hinzu und gehe zunext[node]. - Lösche den Eintrag am Index
length - n. - Gib das Array zurück.
def removeNthFromEnd(values, next, n):
# Write the values out in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Counting from the end, the n-th value sits at index len(order) - n.
del order[len(order) - n]
return orderZähle die Knoten und hebe dann die Verknüpfung auf
Idee
Um einen Knoten aus einer Liste zu entfernen, änderst du die Verknüpfung des Knotens davor, sodass sie ihn überspringt: next[prev] = next[next[prev]]. Der entfernte Knoten befindet sich weiterhin in den Arrays, aber kein Durchlauf vom Kopf aus erreicht ihn jemals wieder.
Finde also prev. Zähle die Knoten bei einem ersten Durchlauf. Wenn der Kopf als Position 0 gezählt wird, befindet sich das Ziel an Position L-n und der Knoten davor an Position L-n-1. Du erreichst ihn vom Kopf aus in L-n-1 Schritten. Im ersten Beispiel gilt L = 5 und n = 2: Zwei Schritte 0 → 2 → 4 bringen dich zu Knoten 4, der mit Knoten 1, der 9, verknüpft ist. Durch Setzen von next[4] = next[1] = 3 ergibt sich die Liste 5, 2, 6, 7.
In einem Fall gibt es keinen Knoten vor dem Ziel: n = L, wenn das Ziel der Kopf ist. Dann muss nichts neu verknüpft werden. Die Liste beginnt dann, wie im zweiten Beispiel, bei next[0] statt bei 0. Gehe anschließend vom Kopf aus durch die Liste, um die Antwort zusammenzustellen. Zwei Durchläufe durch die Liste erfordern etwa 2L Schritte, und zusätzlich zur Antwort werden nur einige Ganzzahlen an Speicher benötigt.
Algorithmus
- Gehe vom Knoten
0bis-1und zähle die Knoten alsL. - Wenn
n == Lgilt, ist der neue Kopfnext[0]. - Andernfalls beginne mit
prevam Knoten0und bewege ihnL-n-1Mal, dann setzenext[prev] = next[next[prev]]. - Gehe vom Kopf aus und sammle
values[node]der Reihe nach.
def removeNthFromEnd(values, next, n):
# First pass: count the nodes.
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
head = 0
if n == length:
# The node to remove is the head, so the list starts at its second node.
head = next[0]
else:
# Second pass: stop on the node just before position length - n.
prev = 0
for _ in range(length - n - 1):
prev = next[prev]
next[prev] = next[next[prev]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return resultZwei Zeiger im Abstand von n Links
Idee
Du kannst „n vom Ende aus“ bestimmen, ohne L zu kennen. Bewege fast um n Links nach vorn, während slow am Kopf wartet. Bewege dann beide jeweils um einen Link weiter. Der Abstand bleibt n, sodass slow auf Position L-1-n steht, wenn fast auf dem letzten Knoten steht (next[fast] == -1, Position L-1): dem Knoten direkt vor dem Ziel. Ein next[slow] = next[next[slow]] entfernt den Zielknoten.
Folge dem ersten Beispiel. fast macht zwei Schritte: 0 → 2 → 4. Nun bewegen sich beide: slow geht zu 2, während fast zu 1 geht, dann geht slow zu 4, während fast zu 3 geht. Knoten 3 ist der letzte, also hältst du an. next[4] ist Knoten 1, die 9, und mit next[4] = next[1] = 3 entfernst du ihn.
Der Fall mit dem Kopf ergibt sich von selbst. Da n ≤ L gilt, erreicht fast während seines Vorsprungs nur dann -1, wenn n = L gilt – und genau dann ist der Kopf das Ziel. Bei Knotenobjekten würdest du einen Dummy-Knoten vor den Kopf setzen, um diesen Fall verschwinden zu lassen; hier erfüllt die Prüfung fast == -1 denselben Zweck. Finden und Entfernen benötigt einen Durchlauf. Die Antwort auszugeben ist ein weiterer Durchlauf, den jeder Ansatz benötigt.
Algorithmus
- Setze
fast = 0und bewege esnMal mitfast = next[fast]. - Wenn
fast == -1, ist der Kopf das Ziel: Der neue Kopf istnext[0]. - Andernfalls setze
slow = 0und bewege beide, solangenext[fast] != -1. - Setze
next[slow] = next[next[slow]]. - Gehe vom Kopf aus weiter und sammle
values[node]der Reihe nach.
def removeNthFromEnd(values, next, n):
# Send fast n links ahead of slow.
fast = 0
for _ in range(n):
fast = next[fast]
head = 0
if fast == -1:
# Fast fell off the end, so the list has exactly n nodes: remove the head.
head = next[0]
else:
# Move both, keeping the gap. When fast stands on the last node,
# slow stands just before the node to remove.
slow = 0
while next[fast] != -1:
slow = next[slow]
fast = next[fast]
next[slow] = next[next[slow]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
Stolperfallen und Grenzfälle
Die meisten falschen Antworten entstehen dadurch, dass der Nachläufer an der falschen Stelle anhält oder der Fall behandelt wird, in dem der Kopf entfernt wird.
- Der Eintrag am Array-Index
L-nwird entfernt. Die Knoten sind nicht in der Reihenfolge der Liste gespeichert, daher verweist dieser Index normalerweise auf einen anderen Knoten. Im ersten Beispiel istvalues[3] = 7der letzte Knoten, nicht die9. - Anhalten, wenn
fast == -1, statt wennnext[fast] == -1. Dadurch rücktsloweinen Schritt zu weit vor und landet beim Zielknoten selbst. In einer einfach verketteten Liste kannst du einen Knoten nicht von diesem Knoten selbst abkoppeln. - Den Fall mit dem Kopf vergessen. Wenn
n = L, istfastnach seinem Start am Kopf-1, und das Lesen vonnext[fast]führt in den meisten Sprachen zu einem Fehler. Python liestnext[-1]ohne Beanstandung und gibt eine falsche Liste zurück, was schwerer zu erkennen ist. - Beim Abkoppeln
next[slow] = next[slow] + 1oderslow + 2verwenden. Benachbarte Knoten in der Liste sind in den Arrays nicht benachbart; der einzige Weg zum Knoten nach dem Ziel führt übernext[next[slow]]. - Die Antwort ab Knoten
0sammeln, nachdem der Kopf entfernt wurde. Beginne den abschließenden Durchlauf beim neuen Kopf. - Den Offset in Lua und R vergessen, wo Arrays bei 1 beginnen. Lass die Knotenindizes bei 0 beginnen und lies
next[node + 1]. Ruby und R reservieren das Wortnext, daher nennen ihre Starter den Parameternext_.
Häufige Fragen4
Wie entfernst du den n-ten Knoten vom Ende einer verketteten Liste in einem Durchlauf?
Verwende zwei Zeiger mit einem Abstand von n. Bewege den ersten n Knoten weiter, dann bewege beide gemeinsam, bis der erste auf dem letzten Knoten steht. Der zweite steht nun direkt vor dem zu entfernenden Knoten, also setzt du seinen Verweis auf den Knoten danach. Wenn der erste Zeiger während seines Vorsprungs über das Ende der Liste hinausläuft, ist der zu entfernende Knoten der Kopf.
Warum verwenden Lösungen für dieses Problem einen Dummy-Knoten?
Das Entfernen eines Knotens bedeutet, den Verweis des Knotens davor zu ändern. Der Kopf hat jedoch keinen Knoten vor sich. Ein Dummy-Knoten vor dem Kopf gibt jedem Knoten, einschließlich des Kopfes, einen Vorgänger, sodass eine einzige Zeile zum Entfernen der Verknüpfung alle Fälle abdeckt. Die Antwort beginnt dann beim nächsten Knoten des Dummy-Knotens. Wenn geprüft wird, ob der führende Zeiger nach n Schritten über das Ende der Liste hinausgelaufen ist, wird derselbe Fall auch ohne zusätzlichen Knoten behandelt.
Wie hoch sind die Zeit- und die Speicherkomplexität beim Entfernen des n-ten Knotens vom Ende?
Für eine Liste mit L Knoten beträgt die Laufzeit O(L), da du das Ende erreichen musst, um zu wissen, wo sich das Ziel befindet. Sowohl das vorherige Zählen als auch die Zwei-Zeiger-Methode benötigen O(1) zusätzlichen Speicher. Das Kopieren der Werte in ein Array benötigt O(L).
Ist die Lösung mit zwei Zeigern schneller, als zuerst die Länge zu zählen?
Nicht viel: Beide sind O(L), und die beiden Zeiger machen zusammen immer noch ungefähr so viele Schritte wie zwei Durchläufe. Der eigentliche Vorteil ist, dass du die Länge nicht im Voraus kennen musst. Deshalb funktioniert die Methode auch, wenn die Liste als Datenstrom ankommt, den du nur einmal lesen kannst. Genau diesen einmaligen Durchlauf verlangen Interviewer meist.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def removeNthFromEnd(values, next, n):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
values = [5, 9, 2, 7, 6] next = [2, 3, 4, -1, 1] n = 2
Erwartet
[5, 2, 6, 7]