Palindrome Linked List

Q: Wie hoch ist die Zeitkomplexität der Überprüfung, ob eine verkettete Liste ein Palindrom ist?

Jeder Ansatz hat für eine Liste mit L Knoten eine Laufzeit von O(L) , da jeder Wert verglichen werden muss. Das Kopieren der Werte in ein Array oder auf einen Stapel benötigt zusätzlichen Speicherplatz von O(L) ; das Umkehren der zweiten Hälfte an Ort und Stelle benötigt O(1) .

Q: Wie finden der schnelle und der langsame Zeiger die Mitte einer verketteten Liste?

Beide starten am Anfang, und der schnelle Zeiger macht für jeden Schritt des langsamen zwei Schritte. Wenn der schnelle Zeiger das Ende erreicht, hat er die gesamte Liste durchlaufen und der langsame die Hälfte davon.

Q: Wird die Eingabe dadurch zerstört, dass die Hälfte der Liste umgekehrt wird?

Ja, dadurch ändern sich die Verknüpfungen der zweiten Hälfte, und in den meisten Sprachen gehört dieses Array dem Aufrufer selbst. Wenn die Liste noch benötigt wird, führe den Vergleich ohne vorzeitige Rückgabe zu Ende und kehre diese Hälfte anschließend wieder um. Der mittlere Knoten verweist weiterhin auf den ersten Knoten der Hälfte, sodass die Liste mit zusätzlichem Speicherbedarf von O(1) wieder vollständig ist.

LeichtVerkettete Liste Schneller und langsamer Zeiger Zwei Zeiger

+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 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.

Gib true zurück, wenn die Werte vom Kopf bis zum Ende genauso gelesen werden wie vom Ende zurück zum Kopf, andernfalls false.

Funktion

isPalindrome(next: integer-array, values: integer-array) → boolean

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ückboolean: wahr, wenn die Liste in beiden Richtungen gleich gelesen wird

Einschränkungen

1 ≤ L ≤ 5000, wobei L die Länge von next und values ist.
-100 ≤ values[i] ≤ 100
Jedes next[i] ist -1 oder ein Knotenindex von 0 bis L-1.
Ausgehend vom Knoten 0 besucht die Liste jeden Knoten genau einmal und erreicht anschließend -1. Es gibt keinen Zyklus.

Beispiele

Eingabe: next = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
Ausgabe: true
Erklärung: Die Verbindungen besuchen die Knoten 0, 4, 1, 3, 2, daher lautet die Liste 3, 1, 4, 1, 3. Die beiden 3er stimmen überein, die beiden 1er stimmen überein, und die 4 in der Mitte hat kein Gegenstück zum Vergleichen.

Eingabe: next = [2, -1, 3, 1]values = [4, 4, 9, 9]
Ausgabe: true
Erklärung: Die Liste besucht die Knoten 0, 2, 3, 1 und liest 4, 9, 9, 4, in beiden Richtungen gleich.

Eingabe: next = [2, -1, 1]values = [1, 2, 1]
Ausgabe: false
Erklärung: Das Array values ist [1, 2, 1], aber die Liste besucht die Knoten 0, 2, 1 und liest 1, 1, 2. Rückwärts ergibt das 2, 1, 1, daher lautet die Antwort false.

Weiterführende Frage

Kannst du es in O(L) Zeit mit O(1) zusätzlichem Speicher schaffen?

Tipps

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

0 von 3 geöffnet

Lösung

Bei einer Palindromprüfung wird jeder Wert seinem Spiegelbild vom anderen Ende gegenübergestellt. Eine einfach verkettete Liste lässt sich nur vorwärts durchlaufen, daher besteht die Schwierigkeit darin, die hintere Hälfte rückwärts zu lesen. Eine Array-Kopie erledigt das mit O(L) Speicher, wobei L die Anzahl der Knoten ist; das Umkehren der Verknüpfungen der zweiten Hälfte erledigt es mit O(1).

Kopiere die Werte in ein Array

Idee

Ein Zeiger ist hier ein Knotenindex, und das Vorwärtsgehen erfolgt mit node = next[node]. Durchlaufe die Liste einmal und kopiere jeden Wert in ein Array, das du von beiden Enden aus lesen kannst. Vergleiche den ersten und den letzten Wert, bewege beide Indizes zur Mitte hin und gib bei jeder Abweichung false zurück. Bei einer ungeraden Länge ist der mittlere Wert sein eigener Partner.

Jeder Wert muss gelesen werden, daher ist eine Laufzeit von O(L) optimal. Der zusätzliche Speicherbedarf beträgt L Ganzzahlen.

Algorithmus

Gehe von Knoten 0 zu -1 und füge jedes values[node] einem Array hinzu.
Setze i = 0 und j auf den letzten Index.
Solange i < j gilt: Gib false zurück, wenn die beiden Werte unterschiedlich sind, andernfalls erhöhe i und verringere j.
Gib true zurück.

def isPalindrome(next, values):
    # Write the values out in list order.
    seq = []
    node = 0
    while node != -1:
        seq.append(values[node])
        node = next[node]
    # Compare from both ends toward the middle.
    i = 0
    j = len(seq) - 1
    while i < j:
        if seq[i] != seq[j]:
            return False
        i += 1
        j -= 1
    return True

Kehre die zweite Hälfte direkt an Ort und Stelle um

Idee

Kehre die Verknüpfungen der hinteren Hälfte um, statt sie zu kopieren: Ein Durchlauf vom alten letzten Knoten führt dann zur Mitte. Um die Mitte zu finden, gehe mit fast zwei Verknüpfungen für jede Verknüpfung weiter, die slow zurücklegt, solange fast zwei Verknüpfungen voraus ist. slow hält am letzten Knoten der ersten Hälfte an, bei ungeradem L also am mittleren Knoten. Im ersten Beispiel geht slow den Weg 0 → 4 → 1, während fast den Weg 0 → 1 → 2 geht, sodass slow bei 4 anhält.

Kehre die Knoten nach slow um und gehe dann gleichzeitig mit left vom Kopf und mit right von der umgekehrten Hälfte aus weiter: 3 mit 3, dann 1 mit 1. Die umgekehrte Hälfte ist nie länger als die erste Hälfte. Wenn du also anhältst, sobald right endet, vergleichst du genau die relevanten Paare. Jede Phase durchläuft höchstens L Knoten und speichert einige Ganzzahlen. In R kopiert das Ändern von next_ den Vektor einmal, daher verwendet R O(L) Speicher.

Algorithmus

Setze slow = fast = 0. Solange next[fast] und next[next[fast]] beide nicht -1 sind, bewege slow um eine Verknüpfung und fast um zwei.
Kehre die Liste um, die bei next[slow] beginnt: Speichere für jeden Knoten seine Verknüpfung, zeige auf prev und bewege dann prev und den Knoten weiter.
Setze left = 0 und right = prev, den Kopf der umgekehrten Hälfte.
Solange right != -1 gilt: Gib bei einer Abweichung false zurück, andernfalls bewege beide Zeiger um eine Verknüpfung weiter.
Gib true zurück.

def isPalindrome(next, values):
    # Find the middle: fast moves two links for every one link slow moves.
    slow = 0
    fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    # slow is the last node of the first half (the middle node when the length is odd).
    # Reverse the links of the second half.
    prev = -1
    node = next[slow]
    while node != -1:
        after = next[node]
        next[node] = prev
        prev = node
        node = after
    # prev is the old last node, now the head of the reversed half.
    left = 0
    right = prev
    while right != -1:
        if values[left] != values[right]:
            return False
        left = next[left]
        right = next[right]
    return True

Stolperfallen und Grenzfälle

Die Arrays statt der Liste prüfen. Im dritten Beispiel ist values [1, 2, 1], aber die Liste lautet 1, 1, 2.
Nur next[fast] != -1 testen. fast kann dann zu -1 springen und next[-1] lesen, was in den meisten Sprachen außerhalb des gültigen Bereichs liegt und in Python und Ruby stillschweigend den letzten Eintrag liefert.
Vergleichen, bis left endet, statt bis right. Der mittlere Knoten ist weiterhin mit der alten zweiten Hälfte verknüpft, daher ist der Durchlauf vom Kopf aus der längere.
next[node] während des Umkehrens überschreiben, bevor es gespeichert wird, wodurch der Rest der Liste verloren geht.
In Lua und R, wo Arrays bei 1 beginnen, next[node] für eine 0-basierte Knoten-ID lesen. Lies next[node + 1].

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der Überprüfung, ob eine verkettete Liste ein Palindrom ist?

Jeder Ansatz hat für eine Liste mit L Knoten eine Laufzeit von O(L), da jeder Wert verglichen werden muss. Das Kopieren der Werte in ein Array oder auf einen Stapel benötigt zusätzlichen Speicherplatz von O(L); das Umkehren der zweiten Hälfte an Ort und Stelle benötigt O(1).

Wie finden der schnelle und der langsame Zeiger die Mitte einer verketteten Liste?

Beide starten am Anfang, und der schnelle Zeiger macht für jeden Schritt des langsamen zwei Schritte. Wenn der schnelle Zeiger das Ende erreicht, hat er die gesamte Liste durchlaufen und der langsame die Hälfte davon.

Wird die Eingabe dadurch zerstört, dass die Hälfte der Liste umgekehrt wird?

Ja, dadurch ändern sich die Verknüpfungen der zweiten Hälfte, und in den meisten Sprachen gehört dieses Array dem Aufrufer selbst. Wenn die Liste noch benötigt wird, führe den Vergleich ohne vorzeitige Rückgabe zu Ende und kehre diese Hälfte anschließend wieder um. Der mittlere Knoten verweist weiterhin auf den ersten Knoten der Hälfte, sodass die Liste mit zusätzlichem Speicherbedarf von O(1) wieder vollständig ist.

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

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

true