Sort List

+10

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 ist mit Knoten next[i] verknüpft. -1 beendet die Liste, und der Kopf ist Knoten 0. Die Knoten sind nicht in Listenreihenfolge gespeichert, und die Arrays können auch übrig gebliebene Knoten enthalten, die beim Durchlaufen ab Knoten 0 nie erreicht werden. Diese gehören nicht zur Liste, selbst wenn ihre Verknüpfungen in die Liste zeigen.

Sortiere die Liste in nicht absteigender Reihenfolge nach dem Wert und gib die Werte ihrer Knoten in dieser Reihenfolge zurück.

Funktion

sortList(next: integer-array, values: integer-array) → integer-array

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 der Listenknoten, beginnend mit dem kleinsten

Einschränkungen

1 ≤ n ≤ 4000, wobei n die Länge von next und values ist.
-1000 ≤ values[i] ≤ 1000
Jedes next[i] ist -1 oder ein Knotenindex von 0 bis n-1.
Ausgehend vom Knoten 0 erreicht die Liste -1, ohne einen Knoten zweimal zu besuchen.
Nodes, die bei der Durchquerung ab Knoten 0 nicht erreicht werden, sind nicht Teil der Liste. Ihre next-Einträge können auf beliebige Stellen verweisen.

Beispiele

Eingabe: next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
Ausgabe: [1, 2, 3, 4, 5]
Erklärung: Der Weg von Knoten 0 besucht die Knoten 0, 3, 2, 4, 1, daher lautet die Liste 4, 2, 3, 5, 1. Sortiert ergibt das 1, 2, 3, 4, 5.

Eingabe: next = [2, 0, -1, -1]values = [6, 9, -2, 5]
Ausgabe: [-2, 6]
Erklärung: Die Liste ist 0 → 2, was 6, -2 ergibt. Die Knoten 1 und 3 werden vom Kopf aus nie erreicht, daher werden ihre Werte 9 und 5 ausgelassen, obwohl Knoten 1 mit Knoten 0 verknüpft ist.

Eingabe: next = [1, 2, 3, -1]values = [3, -1, 3, -1]
Ausgabe: [-1, -1, 3, 3]
Erklärung: Die Liste lautet 3, -1, 3, -1. Gleiche Werte bleiben so oft in der Antwort, wie sie vorkommen: -1, -1, 3, 3.

Weiterführende Frage

Kannst du durch erneutes Verknüpfen der Knoten in O(n log n) Zeit sortieren, ohne die Werte herauszukopieren?

Lösung

Quicksort und Heapsort basieren auf wahlfreiem Zugriff, und eine einfach verkettete Liste kann sich nur vorwärts bewegen. Mergesort eignet sich: Sowohl beim Teilen einer Liste in ihrer Mitte als auch beim Zusammenführen zweier sortierter Listen geht man vorwärts, sodass die Verknüpfungen selbst in O(n log n) sortiert werden. Hier ist n die Länge der Arrays.

Kopiere die Werte in ein Array und sortiere es

Idee

Die Liste besteht aus den Werten, die beim Durchlaufen mit node = next[node] vom Knoten 0 bis -1 besucht werden. Sammle diese Werte in einem neuen Array, sortiere es mit der integrierten Sortierfunktion und gib es zurück. Du kannst values nicht direkt sortieren: Im zweiten Beispiel enthält es 9 und 5, die nicht auf der Liste stehen.

Das Durchlaufen benötigt O(n) und das Sortieren O(n log n), bei zusätzlichem Speicherbedarf von O(n). Die Liste selbst wird nie verändert. Deshalb fragen Interviewer nach dem nächsten Ansatz.

Algorithmus

Beginne mit einem leeren Array und node = 0.
Solange node nicht -1 ist, füge values[node] hinzu und gehe zu next[node].
Sortiere das Array in aufsteigender Reihenfolge und gib es zurück.

def sortList(next, values):
    # Collect the values of the nodes on the list, then sort them.
    on_list = []
    node = 0
    while node != -1:
        on_list.append(values[node])
        node = next[node]
    on_list.sort()
    return on_list

Merge-Sort auf den Verknüpfungen

Idee

Ein langsamer Zeiger, der sich um einen Knoten weiterbewegt, und ein schneller Zeiger, der sich um zwei Knoten weiterbewegt, finden in einem Durchlauf die Mitte. Zum Zusammenführen zweier sortierter Listen genügen ihre jeweils ersten Knoten: Nimm den kleineren und gehe einen Schritt weiter. Für keinen der beiden Schritte wird ein zweites Array benötigt.

Im ersten Beispiel bleibt slow bei der 3 stehen, und durch das Trennen der Verbindung wird 4, 2, 3, 5, 1 in 4, 2, 3 und 5, 1 aufgeteilt. Diese werden zu 2, 3, 4 und 1, 5 sortiert, und beim Zusammenführen werden 1, 2, 3, 4 übernommen; anschließend wird die übrig gebliebene 5 angehängt.

Bei jeder Aufteilungsebene wird jeder Knoten eine konstante Anzahl von Malen bearbeitet, und es gibt etwa log n Ebenen. Daher beträgt die Laufzeit O(n log n). Der einzige zusätzliche Speicherbedarf ist der Rekursionsstapel, der bei 4000 Knoten etwa 12 Aufrufe tief ist.

Algorithmus

Wenn die Liste einen Knoten hat (next[head] == -1), gib head zurück.
Setze slow = head und fast = next[head]; bewege slow um einen Link und fast um zwei, solange fast und next[fast] nicht -1 sind.
Setze second = next[slow] und trenne die Liste mit next[slow] = -1.
Sortiere beide Hälften rekursiv. Füge sie zusammen: Verknüpfe den kleineren vorderen Knoten nach tail, bis eine Hälfte leer ist, und verknüpfe dann den Rest der anderen Hälfte.
Gehe vom zurückgegebenen Kopf aus durch die Liste und sammle die Werte.

def sortList(next, values):
    def merge(a, b):
        # Splice two sorted lists into one; on a tie the node from a goes first.
        head = tail = -1
        while a != -1 and b != -1:
            if values[b] < values[a]:
                node, b = b, next[b]
            else:
                node, a = a, next[a]
            if tail == -1:
                head = node
            else:
                next[tail] = node
            tail = node
        next[tail] = a if a != -1 else b  # attach whatever is left
        return head

    def sort(head):
        if next[head] == -1:  # one node is already sorted
            return head
        # slow stops on the last node of the first half
        slow, fast = head, next[head]
        while fast != -1 and next[fast] != -1:
            slow = next[slow]
            fast = next[next[fast]]
        second = next[slow]
        next[slow] = -1  # cut the list in two
        return merge(sort(head), sort(second))

    result = []
    node = sort(0)
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Stolperfallen und Grenzfälle

Das gesamte values-Array sortieren. Im zweiten Beispiel werden dadurch 9 und 5 eingefügt, die nicht in der Liste stehen.
fast am Kopf starten lassen. Bei zwei Knoten landet slow dann auf dem zweiten Knoten, durch das Trennen bleibt die zweite Hälfte leer und die Rekursion verkleinert sich nie.
Das Trennen mit next[slow] = -1 vergessen. Die erste Hälfte läuft dann in die zweite hinein, und beide Aufrufe sortieren überlappende Listen.
Den Rest einer Hälfte verwerfen, wenn der anderen die Knoten ausgehen. Diese Knoten verschwinden aus dem Ergebnis.
In Lua und R beginnen Arrays bei 1: Lass die Knotenindizes bei 0 beginnen und lies next[node + 1]. Die R-Version kopiert das Verbindungsarray einmal und verwendet daher O(n) zusätzlichen Speicher.

Häufige Fragen3

Wie sortiert man eine verkettete Liste am besten?

Mergesort. Beim Aufteilen in der Mitte, Sortieren beider Hälften und Zusammenführen durchläuft man die Liste stets vorwärts – die einzige Richtung, die eine einfach verkettete Liste unterstützt. Der Algorithmus läuft in O(n log n) Zeit und verkettet die vorhandenen Knoten neu.

Warum wird Mergesort für verkettete Listen gegenüber Quicksort bevorzugt?

Quicksort kann eine Liste durch Umverknüpfen partitionieren, aber ein guter Pivot erfordert wahlfreien Zugriff, und wenn der Kopf als Pivot verwendet wird, kostet eine sortierte Liste O(n²). Merge Sort teilt immer in zwei Hälften, sodass die Laufzeit bei jeder Eingabe O(n log n) bleibt.

Kannst du eine verkettete Liste in O(n log n) Zeit und mit O(1) Speicher sortieren?

Ja, mit Bottom-up-Mergesort. Dabei werden benachbarte Läufe der Länge 1, dann 2, dann 4 zusammengeführt, bis ein Lauf die Liste abdeckt. Es gibt log n lineare Durchläufe, und der einzige Speicherbedarf besteht aus einigen Knotenindizes.

def sortList(next, values):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

next = [3, -1, 4, 2, 1]
values = [4, 1, 3, 2, 5]

Erwartete Ausgabe

[1, 2, 3, 4, 5]