Reorder 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 verweist auf den Knoten next[i], -1 beendet die Liste und der Kopf ist Knoten 0. Die Knoten sind nicht in der Reihenfolge der Liste gespeichert, folge also den Verweisen.
Nenne die Knoten in der Reihenfolge der Liste L0, L1, ..., Lk. Ordne die Liste so um, dass sie der Reihenfolge L0, Lk, L1, Lk-1, L2, Lk-2, ... folgt: zuerst der erste Knoten, dann der letzte, dann der zweite, dann der vorletzte und so weiter. Gib die Werte in dieser neuen Reihenfolge zurück.
Funktion
- nextinteger-array
- der Index des Knotens, auf den jeder Knoten verweist, oder -1 für den letzten Knoten
- valuesinteger-array
- der von jedem Knoten gehaltene Wert
- Gibt zurückinteger-array
- die Werte in der Reihenfolge der neu sortierten Liste
Einschränkungen
1 ≤ n ≤ 4000, wobeindie Länge vonnextund vonvaluesist.-1000 ≤ values[i] ≤ 1000- Jedes
next[i]ist-1oder ein Knotenindex von0bisn-1. - Ausgehend von Knoten
0besucht die Liste jeden Knoten genau einmal und erreicht dann-1. Es gibt keinen Zyklus.
Beispiele
- Eingabe
- next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
- Ausgabe
- [1, 5, 2, 4, 3]
- Erklärung
- Wenn man den Verknüpfungen vom Knoten
0folgt, lautet die Liste1, 2, 3, 4, 5. Der erste, der letzte, der zweite und der vorletzte Wert ergeben1, 5, 2, 4, und der mittlere Wert3kommt zuletzt.
- Eingabe
- next = [2, 3, 1, -1]values = [10, 30, 20, 40]
- Ausgabe
- [10, 40, 20, 30]
- Erklärung
- Die Liste besucht die Knoten
0, 2, 1, 3und liest10, 20, 30, 40. Das erste und das letzte ergeben10, 40, danach ergibt das innere Paar20, 30.
- Eingabe
- next = [-1]values = [7]
- Ausgabe
- [7]
- Erklärung
- Bei einer Liste mit einem Knoten gibt es nichts zu verschieben, daher lautet die Antwort
[7].
Weiterführende Frage
Kannst du die Links selbst mit O(1) zusätzlichem Speicher neu anordnen?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Schreibe die Zielreihenfolge für
1, 2, 3, 4, 5, 6. Welche Knoten stammen aus der vorderen Hälfte der Liste, und in welcher Reihenfolge erscheinen die Knoten der hinteren Hälfte?Die hintere Hälfte erscheint rückwärts:
6, 5, 4. Wenn die hintere Hälfte umgekehrt wäre, bestünde die Antwort aus zwei Listen, die zusammengeführt werden, indem abwechselnd jeweils ein Knoten aus jeder Liste genommen wird.Finde die Mitte mit einem langsamen Zeiger, der sich um einen Knoten weiterbewegt, und einem schnellen Zeiger, der sich um zwei Knoten weiterbewegt. Trenne die Liste hinter der Mitte, kehre den zweiten Teil um, indem du seine Verknüpfungen umdrehst, und verzahne anschließend die beiden Teile Knoten für Knoten miteinander.
Lösung
Die neue Reihenfolge wechselt zwischen vorne und hinten, aber eine einfach verkettete Liste lässt sich nur vorwärts durchlaufen. Teile die Aufgabe in drei übliche Listenoperationen auf: Finde die Mitte mit langsamen und schnellen Zeigern, kehre die hintere Hälfte um und füge die beiden Hälften knotenweise abwechselnd zusammen.
Bewege den Schwanz jeweils um einen Knoten vorwärts
Idee
Ein Zeiger ist hier ein Knotenindex, und weiterzugehen bedeutet node = next[node]. Nach dem ersten Knoten kommt der letzte, also hänge den letzten Knoten aus und füge ihn nach dem aktuellen ein. Wiederhole das dann zwei Knoten weiter. Für 1, 2, 3, 4, 5 ergibt das 1, 5, 2, 3, 4, dann 1, 5, 2, 4, 3. Stoppe, wenn dem aktuellen Knoten weniger als zwei Knoten folgen.
Den Knoten vor dem letzten zu finden, erfordert in jeder Runde einen Durchlauf bis zum Ende. Die Durchläufe werden pro Runde um zwei Knoten kürzer, insgesamt sind es etwa n²/4 Schritte: vier Millionen bei 4000 Knoten.
Algorithmus
- Setze
cur = 0. - Solange mindestens zwei Knoten auf
curfolgen, gehe mitbeforevoncuraus weiter, bisnext[next[before]] == -1gilt, sodasstail = next[before]der letzte Knoten ist. - Hänge ihn aus, indem du
next[before] = -1setzt, und füge ihn dann ein:next[tail] = next[cur]undnext[cur] = tail. - Setze
curaufnext[tail]und wiederhole den Vorgang. - Gehe von Knoten
0aus weiter und sammle die Werte.
def reorderList(next, values):
cur = 0
# While at least two nodes follow cur, move the last node right after cur.
while next[cur] != -1 and next[next[cur]] != -1:
before = cur
while next[next[before]] != -1: # find the node before the tail
before = next[before]
tail = next[before]
next[before] = -1
next[tail] = next[cur]
next[cur] = tail
cur = next[tail]
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return resultKopiere die Werte und lies von beiden Enden
Idee
Ein Array erreicht sein letztes Element in einem Schritt. Kopiere die Werte in der Reihenfolge der Liste, [1, 2, 3, 4, 5] im ersten Beispiel, und lies dann mit lo von vorne und mit hi von hinten: Nimm lo, nimm hi und bewege beide nach innen, solange lo < hi. Das ergibt 1, 5, 2, 4; bei einer ungeraden Länge treffen beide in der Mitte auf die 3, die zuletzt kommt.
Das benötigt O(n) Zeit und O(n) zusätzlichen Speicher, und die Verknüpfungen ändern sich nie.
Algorithmus
- Gehe von Knoten
0aus und füge jeden Wert aninOrderan. - Setze
lo = 0undhiauf den letzten Index. - Solange
lo < higilt, fügeinOrder[lo]undinOrder[hi]an und erhöhe anschließendlound verringerehi. - Wenn
lo == higilt, füge den mittleren Wert an.
def reorderList(next, values):
# Write the values out in list order.
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
# Take from the front and the back in turn.
result = []
lo, hi = 0, len(in_order) - 1
while lo < hi:
result.append(in_order[lo])
result.append(in_order[hi])
lo += 1
hi -= 1
if lo == hi: # odd length: the middle value comes last
result.append(in_order[lo])
return resultFinde die Mitte, kehre die hintere Hälfte um, verflechte
Idee
Für 1, 2, 3, 4, 5, 6 lautet die Antwort 1, 6, 2, 5, 3, 4: die vordere Hälfte 1, 2, 3 der Reihe nach, abwechselnd mit der rückwärts gelesenen hinteren Hälfte 4, 5, 6. Teile die Liste also in der Mitte, kehre die hintere Hälfte um und verflechte sie.
slow bewegt sich um einen Link weiter, während fast sich um zwei weiterbewegt. Daher bleibt slow beim letzten Knoten der vorderen Hälfte stehen: bei der 3, sowohl bei fünf als auch bei sechs Knoten. Wird danach getrennt, hat die vordere Hälfte bei ungerader Länge den zusätzlichen Knoten, und dieser Knoten bildet das Ende der Antwort. Beim Verflechten wird abwechselnd je ein Knoten aus jeder Hälfte genommen, bis die hintere Hälfte aufgebraucht ist.
Jeder Knoten wird eine konstante Anzahl von Malen berührt, und es werden nur einige Indizes Speicherplatz benötigt. R kopiert den Link-Vektor bei seiner ersten Änderung, daher beträgt der Speicherbedarf in R O(n).
Algorithmus
- Bewege
slowum einen Knoten undfastum zwei Knoten, solangenext[fast]undnext[next[fast]]nicht-1sind. - Setze
second = next[slow], dannnext[slow] = -1. - Kehre die Liste um, die bei
secondbeginnt; ihr neuer Kopf istprev. - Verflechte: Verknüpfe, solange
secondnicht-1ist,firstmitsecondundsecondmit dem altennext[first], und rücke dann beide weiter. - Gehe vom Knoten
0aus die Liste entlang und sammle die Werte.
def reorderList(next, values):
# 1. Find the middle: slow stops on the last node of the first half.
slow = fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
# 2. Reverse the second half.
prev = -1
while second != -1:
after = next[second]
next[second] = prev
prev = second
second = after
# 3. Weave: one node from the front half, one from the reversed back half.
first, second = 0, prev
while second != -1:
first_after, second_after = next[first], next[second]
next[first] = second
next[second] = first_after
first, second = first_after, second_after
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return result
Stolperfallen und Grenzfälle
- Die Liste nicht nach der Mitte abzuschneiden. Ohne
next[slow] = -1zeigt die vordere Hälfte weiterhin auf die hintere Hälfte, und nach dem Zusammenflechten läuft die Liste wieder in sich selbst zurück. - Einen Verweis zu überschreiben, bevor er gespeichert wurde. Beim Umkehren und Zusammenflechten zuerst
next[node]in eine Variable einlesen, sonst geht der Rest der Liste verloren. - Zusammenzuflechten, bis die vordere Hälfte endet. Bei einer ungeraden Länge läuft diese Schleife noch einmal, wenn
secondauf-1steht, und liestnext[-1]. - Die Reihenfolge im Array mit der Reihenfolge in der Liste zu verwechseln. Im ersten Beispiel ist
valuesgleich[1, 3, 5, 2, 4], aber die Liste lautet1, 2, 3, 4, 5. - In Lua und R beginnen Arrays bei 1. Die Knotenindizes bleiben bei 0 und es wird
next[node + 1]gelesen.
Häufige Fragen3
Warum die zweite Hälfte der Liste umkehren?
Die Antwort liest die hintere Hälfte vom letzten bis zum ersten Knoten, und eine einfach verkettete Liste lässt sich nur vorwärts durchlaufen. Wenn man die hintere Hälfte einmal in O(n) umkehrt, kann die Zusammenführung beide Hälften vorwärts durchlaufen.
Wie hoch ist die Zeitkomplexität von Reorder List?
Die In-place-Methode läuft in O(n) Zeit mit O(1) zusätzlichem Speicher: Das Finden der Mitte, das Umkehren und das Verzahnen besuchen jeden Knoten jeweils eine konstante Anzahl von Malen. Das Kopieren der Werte in ein Array benötigt ebenfalls O(n) Zeit, aber O(n) Speicher, und das schrittweise Verschieben des Endes um jeweils einen Knoten benötigt O(n²).
Wo liegt die Mitte, wenn die Liste eine gerade Anzahl von Knoten hat?
Halte den langsamen Zeiger beim letzten Knoten der vorderen Hälfte an. Bei sechs Knoten bestehen die Hälften aus drei und drei; bei fünf aus drei und zwei. Der zusätzliche Knoten schließt dann die Antwort ab, denn dort steht in der sortierten Reihenfolge der mittlere Wert.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def reorderList(next, values):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
next = [3, 4, -1, 1, 2] values = [1, 3, 5, 2, 4]
Erwartete Ausgabe
[1, 5, 2, 4, 3]