Intersection of Two Linked Lists

+10

Due liste concatenate singolarmente vivono in un unico insieme di nodi. Il nodo i punta al nodo next[i] e -1 termina una lista. La lista A inizia dal nodo headA e la lista B dal nodo headB. I nodi non sono memorizzati in un ordine particolare, quindi segui i collegamenti.

Le due liste possono convergere: a partire da un certo nodo, proseguono attraverso gli stessi nodi fino alla fine. Restituisci l’indice del primo nodo presente in entrambe le liste, oppure -1 se non condividono alcun nodo.

Funzione

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

nextinteger-array: l'indice del nodo a cui rimanda ciascun nodo, oppure -1 per l'ultimo nodo di una lista
headAinteger: il primo nodo della lista A
headBinteger: il primo nodo della lista B
Restituisceinteger: il primo nodo condiviso dalle due liste, oppure -1

Vincoli

2 ≤ n ≤ 10⁴, dove n è la lunghezza di next.
Ogni next[i] è -1 oppure un indice di nodo da 0 a n-1.
0 ≤ headA, headB ≤ n-1 e headA ≠ headB.
Entrambi gli elenchi terminano con -1 senza visitare due volte alcun nodo. Non c’è alcun ciclo.
Ogni nodo è nell'elenco A, nell'elenco B o in entrambi.

Esempi

Input: next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
Output: 1
Spiegazione: A visita 3, 5, 1, 4, 0 e B visita 2, 1, 4, 0. A partire dal nodo 1 condividono ogni nodo e nessun nodo precedente di A si trova in B, quindi la risposta è 1.

Input: next = [2, 3, 4, -1, -1]headA = 0headB = 1
Output: -1
Spiegazione: La lista A è 0, 2, 4 e la lista B è 1, 3. Entrambe terminano in -1 senza toccare un nodo comune, quindi la risposta è -1.

Input: next = [3, 2, 0, -1]headA = 1headB = 0
Output: 0
Spiegazione: La lista A è 1, 2, 0, 3 e la lista B è 0, 3. La lista B è la coda della lista A, quindi il primo nodo condiviso è headB stesso, il nodo 0.

Per approfondire

Riesci a trovare il nodo in O(m + k) tempo con O(1) memoria aggiuntiva?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Un nodo ha un solo next, quindi due liste che si incontrano non si separano più. Formano una Y, due inizi separati che si uniscono in una coda condivisa, e la risposta è il punto di congiunzione. Gli inizi possono avere lunghezze diverse, quindi percorrere entrambe le liste insieme non individua il punto di congiunzione. Qui sotto, m e k sono le lunghezze di A e B.

Controlla ogni nodo di A rispetto a tutti i nodi di B

Corretto, ma non termina sui test più grandi

Intuizione

Un puntatore è un indice di nodo e avanzare significa node = next[node]. Per ogni nodo a di A, nell'ordine, scorri tutti i nodi di B e confronta ciascun nodo con a. Il primo a che corrisponde è la risposta, perché tutti i nodi precedenti di A non hanno già trovato corrispondenza. Riesamina B per ogni nodo di A: con 5000 nodi in ciascuna lista e nessun nodo condiviso, sono 2.5 × 10^7 confronti.

Algoritmo

Imposta a = headA.
Mentre a non è -1, percorri b da headB fino a -1.
Se in qualsiasi momento b == a, restituisci a.
Altrimenti, sposta a = next[a] e ripeti.
Se la lista A si esaurisce, restituisci -1.

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

Contrassegna i nodi della lista B

Intuizione

Rispondi «questo nodo è in B?» una volta per ogni nodo: percorri B e contrassegna ogni nodo in un array booleano di dimensione n. Gli indici dei nodi sono numeri interi piccoli, quindi un array svolge il compito di un insieme hash. Poi percorri A dalla testa. Il primo nodo contrassegnato è presente in entrambe le liste ed è il primo nodo di questo tipo, perché percorri A in ordine. Nel primo esempio B contrassegna 2, 1, 4, 0 e il percorso lungo A passa per 3 e 5 prima di fermarsi su 1. Ogni lista viene percorsa una volta, quindi il tempo è O(m + k), al costo di n contrassegni.

Algoritmo

Crea onB, un array di n valori booleani impostati su false.
Percorri la lista B da headB e imposta onB[node] = true per ogni nodo.
Percorri la lista A da headA. Restituisci il primo nodo per cui onB[node] è true.
Se la lista A termina, restituisci -1.

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

Due puntatori che si alternano tra le liste

Intuizione

Dividi ciascuna lista nel punto di congiunzione: A ha x nodi privati, poi i c nodi condivisi, e B ha y nodi privati, poi gli stessi c. Il puntatore a percorre A, passa su -1, poi riparte da headB e raggiunge il punto di congiunzione per la seconda volta dopo x + c + 1 + y spostamenti. Il puntatore b percorre B, poi A, e arriva dopo y + c + 1 + x spostamenti. I totali coincidono. Nel primo esempio x = 2, y = 1 e c = 3, ed entrambi si trovano sul nodo 1 dopo sette spostamenti.

Se non c'è una coda condivisa, entrambi i puntatori si trovano su -1 dopo m + 1 + k spostamenti (dopo m quando m = k), e il ciclo restituisce -1. Questa fermata comune è il motivo per cui ciascun puntatore passa su -1 prima di cambiare lista. Ogni puntatore si sposta al massimo m + k + 1 volte, usando la memoria di due indici.

Algoritmo

Imposta a = headA e b = headB.
Finché a != b: sposta a a headB se è -1, altrimenti a next[a].
Nello stesso turno, sposta b a headA se è -1, altrimenti a next[b].
Quando il ciclo termina, restituisci a. È il primo nodo condiviso oppure -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

Trappole e casi limite

Passare dall’ultimo nodo direttamente all’altra testa, saltando la sosta su -1. Quando le liste non condividono alcun elemento, i puntatori non assumono mai lo stesso valore e il ciclo continua all’infinito.
Riavviare un puntatore dalla propria testa. Ogni puntatore percorre quindi la propria lista, e i due si incontrano solo quando i giri coincidono, il che può richiedere fino a (m + 1)·(k + 1) spostamenti.
Considerare l’ordine dell’array come l’ordine della lista. Il nodo 0 è una testa solo se lo indica headA o headB, e gli elementi vicini nell’array non sono nodi vicini nella lista.
In Lua e R, dimenticare che gli array iniziano da 1. Mantieni gli indici dei nodi a base 0 e leggi next[node + 1].

Domande frequenti3

Come trovi il punto in cui due liste concatenate si intersecano senza usare memoria aggiuntiva?

Fai avanzare due puntatori. Ognuno percorre la propria lista e, dopo aver superato la fine, riparte dalla testa dell’altra lista. Entrambi percorrono la stessa distanza totale, quindi raggiungono il primo nodo condiviso nello stesso momento oppure arrivano insieme alla fine, se non ce n’è uno.

Riesci a trovare l’intersezione confrontando le lunghezze degli elenchi?

Sì. Conta i nodi di entrambe le liste, sposta in avanti il puntatore sulla lista più lunga di un numero di posizioni pari alla differenza, poi sposta entrambi di un passo alla volta finché non sono uguali. Anche questo richiede un tempo O(m + k) e una memoria O(1); il metodo di scambio ottiene lo stesso allineamento senza i due passaggi di conteggio.

Qual è la complessità temporale per trovare l’intersezione di due liste collegate?

I metodi dei due puntatori e della lunghezza richiedono un tempo O(m + k) e memoria aggiuntiva O(1). Memorizzare una lista in un set o in un array di marcatori è anch’esso un approccio lineare, ma richiede memoria per quella lista. Confrontare ogni coppia di nodi richiede O(m·k).

def getIntersectionNode(next, headA, headB):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

Intersection of Two Linked Lists

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Controlla ogni nodo di A rispetto a tutti i nodi di B

Contrassegna i nodi della lista B

Due puntatori che si alternano tra le liste

Trappole e casi limite

Domande frequenti3

Problemi simili