Intersection of Two Linked Lists

+10

Zwei einfach verkettete Listen befinden sich in einem gemeinsamen Knotenpool. Knoten i verweist auf Knoten next[i], und -1 beendet eine Liste. Liste A beginnt bei Knoten headA und Liste B bei Knoten headB. Die Knoten sind in keiner bestimmten Reihenfolge gespeichert, folge also den Verweisen.

Die beiden Listen können aufeinander treffen: Ab einem bestimmten Knoten verlaufen sie bis zum Ende über dieselben Knoten. Gib den Index des ersten Knotens zurück, der in beiden Listen vorkommt, oder -1, wenn sie keinen Knoten gemeinsam haben.

Funktion

getIntersectionNode(next: integer-array, headA: integer, headB: integer) → integer

nextinteger-array: der Index des Knotens, auf den jeder Knoten verweist, oder -1 für den letzten Knoten einer Liste
headAinteger: der erste Knoten von Liste A
headBinteger: der erste Knoten der Liste B
Gibt zurückinteger: der erste Knoten, den die beiden Listen gemeinsam haben, oder -1

Einschränkungen

2 ≤ n ≤ 10⁴, wobei n die Länge von next ist.
Jedes next[i] ist -1 oder ein Knotenindex von 0 bis n-1.
0 ≤ headA, headB ≤ n-1 und headA ≠ headB.
Beide Listen enden bei -1, ohne einen Knoten zweimal zu besuchen. Es gibt keinen Zyklus.
Jeder Knoten befindet sich in Liste A, in Liste B oder in beiden.

Beispiele

Eingabe: next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
Ausgabe: 1
Erklärung: A besucht 3, 5, 1, 4, 0 und B besucht 2, 1, 4, 0. Ab Knoten 1 teilen sie sich jeden Knoten, und kein früherer Knoten von A liegt auf B, also lautet die Antwort 1.

Eingabe: next = [2, 3, 4, -1, -1]headA = 0headB = 1
Ausgabe: -1
Erklärung: Liste A ist 0, 2, 4 und Liste B ist 1, 3. Beide enden bei -1, ohne einen gemeinsamen Knoten zu berühren, also lautet die Antwort -1.

Eingabe: next = [3, 2, 0, -1]headA = 1headB = 0
Ausgabe: 0
Erklärung: Liste A ist 1, 2, 0, 3 und Liste B ist 0, 3. Liste B ist der Nachlauf von Liste A, daher ist der erste gemeinsame Knoten headB selbst, der Knoten 0.

Weiterführende Frage

Kannst du den Knoten in O(m + k) Zeit mit O(1) zusätzlichem Speicher finden?

Tipps

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

0 von 3 geöffnet

Lösung

Ein Knoten hat ein next, daher trennen sich zwei Listen, die sich treffen, nie wieder. Sie bilden ein Y: zwei private Anfänge, die zu einem gemeinsamen Ende zusammenlaufen, und die Antwort ist der Treffpunkt. Die Anfänge können unterschiedlich lang sein, sodass gleichzeitiges Durchlaufen beider Listen den Treffpunkt verfehlt. Unten sind m und k die Längen von A und B.

Vergleiche jeden Knoten von A mit allen Knoten von B

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Ein Zeiger ist ein Knotenindex, und vorwärtszugehen bedeutet node = next[node]. Gehe für jeden Knoten a von A der Reihe nach alle Knoten von B durch und vergleiche jeden Knoten mit a. Das erste a, das übereinstimmt, ist die Antwort, denn jeder frühere Knoten von A hat bereits nicht übereingestimmt. Dabei wird B für jeden Knoten von A erneut durchsucht: Bei 5000 Knoten in jeder Liste und keinem gemeinsamen Knoten sind das 2.5 × 10^7 Vergleiche.

Algorithmus

Setze a = headA.
Solange a nicht -1 ist, durchlaufe b von headB bis -1.
Falls b == a irgendwann zutrifft, gib a zurück.
Andernfalls setze a = next[a] und wiederhole den Vorgang.
Wenn Liste A zu Ende ist, gib -1 zurück.

def getIntersectionNode(next, headA, headB):
    a = headA
    while a != -1:
        # Is node a also on list B? Walk all of B to find out.
        b = headB
        while b != -1:
            if a == b:
                return a
            b = next[b]
        a = next[a]
    return -1

Markiere die Knoten von Liste B

Idee

Beantworte für jeden Knoten einmal „Ist dieser Knoten auf B?“: Durchlaufe B und markiere jeden Knoten in einem booleschen Array der Größe n. Die Knotenindizes sind kleine Ganzzahlen, daher erfüllt ein Array den Zweck einer Hash-Menge. Durchlaufe dann A von seinem Kopf aus. Der erste markierte Knoten steht auf beiden Listen, und es ist der erste solche Knoten, weil du A der Reihe nach durchläufst. Im ersten Beispiel markiert B 2, 1, 4, 0, und der Durchlauf entlang A passiert 3 und 5, bevor er bei 1 stoppt. Jede Liste wird einmal durchlaufen, daher beträgt die Laufzeit O(m + k), bei einem Aufwand von n Markierungen.

Algorithmus

Erstelle onB, ein Array aus n booleschen Werten, die auf false gesetzt sind.
Durchlaufe Liste B ab headB und setze für jeden Knoten onB[node] = true.
Durchlaufe Liste A ab headA. Gib den ersten Knoten zurück, für den onB[node] true ist.
Wenn Liste A endet, gib -1 zurück.

def getIntersectionNode(next, headA, headB):
    # Mark every node of list B.
    on_b = [False] * len(next)
    node = headB
    while node != -1:
        on_b[node] = True
        node = next[node]
    # The first marked node on list A is the meeting point.
    node = headA
    while node != -1:
        if on_b[node]:
            return node
        node = next[node]
    return -1

Zwei Zeiger, die zwischen Listen wechseln

Idee

Teile jede Liste an der Verbindungsstelle auf: A besteht aus x privaten Knoten, gefolgt von den c gemeinsam genutzten, und B aus y privaten Knoten, gefolgt von denselben c. Zeiger a durchläuft A, geht zu -1, startet dann bei headB neu und erreicht die Verbindungsstelle zum zweiten Mal nach x + c + 1 + y Schritten. Zeiger b durchläuft B und dann A und kommt nach y + c + 1 + x Schritten an. Die Gesamtzahlen stimmen überein. Im ersten Beispiel gilt x = 2, y = 1 und c = 3, und beide stehen nach sieben Schritten auf Knoten 1.

Bei einem nicht gemeinsam genutzten Ende stehen beide Zeiger nach m + 1 + k Schritten auf -1 (nach m Schritten, wenn m = k), und die Schleife gibt -1 zurück. Dieser gemeinsame Haltepunkt ist der Grund, warum jeder Zeiger zu -1 geht, bevor er wechselt. Jeder Zeiger bewegt sich höchstens m + k + 1 Mal, bei einem Speicherbedarf von zwei Indizes.

Algorithmus

Setze a = headA und b = headB.
Solange a != b: Bewege a zu headB, wenn es -1 ist, andernfalls zu next[a].
Bewege in derselben Runde b zu headA, wenn es -1 ist, andernfalls zu next[b].
Wenn die Schleife endet, gib a zurück. Es ist der erste gemeinsame Knoten oder -1.

def getIntersectionNode(next, headA, headB):
    a, b = headA, headB
    # Each pointer walks its own list, then the other one. Both cover
    # the same number of nodes, so they reach the meeting node together,
    # or reach -1 together when there is none.
    while a != b:
        a = headB if a == -1 else next[a]
        b = headA if b == -1 else next[b]
    return a

Stolperfallen und Grenzfälle

Vom letzten Knoten direkt zum anderen Kopf wechseln und dabei den Halt bei -1 überspringen. Wenn die Listen keine Knoten gemeinsam haben, enthalten die Zeiger nie denselben Wert und die Schleife läuft endlos.
Einen Zeiger an seinem eigenen Kopf neu starten. Jeder Zeiger durchläuft dann wiederholt seine eigene Liste, und sie treffen sich nur, wenn die Durchläufe zusammenpassen, was bis zu (m + 1)·(k + 1) Schritte dauern kann.
Die Reihenfolge im Array mit der Listenreihenfolge gleichsetzen. Knoten 0 ist nur dann ein Kopf, wenn headA oder headB dies angibt, und benachbarte Elemente im Array sind keine benachbarten Knoten in einer Liste.
In Lua und R vergessen, dass Arrays bei 1 beginnen. Knotenindizes weiterhin bei 0 beginnen lassen und next[node + 1] lesen.

Häufige Fragen3

Wie findest du heraus, wo sich zwei verkettete Listen schneiden, ohne zusätzlichen Speicher zu verwenden?

Führe zwei Zeiger aus. Jeder durchläuft seine eigene Liste und setzt nach dem Ende beim Anfang der jeweils anderen Liste fort. Beide legen dieselbe Gesamtstrecke zurück und erreichen daher gleichzeitig den ersten gemeinsamen Knoten oder, falls es keinen gibt, gemeinsam das Ende.

Kannst du die Schnittmenge finden, indem du die Längen der Listen vergleichst?

Ja. Zähle die Knoten beider Listen, bewege den Zeiger in der längeren Liste um die Differenz nach vorne und bewege dann beide jeweils einen Schritt weiter, bis sie gleich sind. Das benötigt ebenfalls O(m + k) Zeit und O(1) Speicher; die Wechselmethode erreicht dieselbe Ausrichtung ohne die beiden Zähldurchläufe.

Wie hoch ist die Zeitkomplexität beim Finden des Schnittpunkts zweier verketteter Listen?

Die Methoden mit zwei Zeigern und Längenberechnung laufen in O(m + k) Zeit und benötigen O(1) zusätzlichen Speicher. Eine Liste in einer Menge oder einem Markierungsarray zu speichern, ist ebenfalls linear, benötigt aber Speicher für diese Liste. Der Vergleich jedes Knotenpaars benötigt O(m·k).

def getIntersectionNode(next, headA, headB):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

next = [-1, 4, 1, 5, 0, 1]
headA = 3
headB = 2

Erwartete Ausgabe

Intersection of Two Linked Lists

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Vergleiche jeden Knoten von A mit allen Knoten von B

Markiere die Knoten von Liste B

Zwei Zeiger, die zwischen Listen wechseln

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben