Individuazione del nodo intersecante da due elenchi collegati intersecanti

Question

Supponiamo che ci siano due elenchi concatenati singoli che si intersecano in un punto e diventano una singola lista collegata.

I puntatori di testa o di inizio di entrambi gli elenchi sono noti, ma il nodo intersecante non è noto. Inoltre, il numero di nodi in ciascuna lista prima di intersecare è sconosciuto e entrambi gli elenchi possono averlo diverso, ad esempio List1 potrebbe avere n nodi prima che raggiunga il punto di intersezione e List2 potrebbe avere m nodi prima che raggiunga il punto di intersezione dove m e n potrebbero essere

• m = n,
• m < n o
• m> n

Un noto o semplice soluzione è quella di confrontare ogni puntatore nodo nel primo elenco con ogni altro puntatore nodo nella seconda lista da cui il nodo corrispondente poi le reti ci porteranno al nodo intersecante. Ma la complessità temporale in questo caso sarà O (n) che sarà alta.

Qual è il modo più efficace per trovare il nodo intersecante?

Answer 1

Questo richiede O (M + N) tempo e O (1) spazio, dove M e N sono la lunghezza totale degli elenchi collegati. Forse inefficiente se la parte comune è molto lungo (cioè M, N >> m, n)

1. Traverse i due lista collegata per trovare M e N.
2. tornare alle teste, poi traverse | M − N | nodi nella lista più lunga.
3. Ora cammina nella fase di blocco e confronta i nodi finché non trovi quelli comuni.

---

Edit: Vedere http://richardhartersworld.com/cri/2008/linkedlist.html

Answer 2

Se possibile, si potrebbe aggiungere un campo di 'colore' o simili ai nodi. Scorri una delle liste, colorando i nodi mentre vai. Quindi scorrere il secondo elenco. Non appena raggiungi un nodo che è già colorato, hai trovato l'intersezione.

Answer 3

Eseguire il dump del contenuto (o dell'indirizzo) di entrambi gli elenchi in una tabella hash. la prima collisione è la tua intersezione.

Answer 4

Controllare gli ultimi nodi di ogni elenco. Se c'è un'intersezione, il loro ultimo nodo sarà lo stesso.

Answer 5

Questa è la soluzione pazza che ho trovato durante la codifica a tarda notte, si 2x più lento di risposta accettata, ma utilizza un bel trucco aritmetica:

public ListNode findIntersection(ListNode a, ListNode b) { 
    if (a == null || b == null) 
     return null; 

    int A = a.count(); 
    int B = b.count(); 

    ListNode reversedB = b.reverse(); 

    // L = a elements + 1 c element + b elements 
    int L = a.count(); 

    // restore b 
    reversedB.reverse(); 

    // A = a + c 
    // B = b + c 
    // L = a + b + 1 

    int cIndex = ((A+B) - (L-1))/2; 
    return a.atIndex(A - cIndex); 
} 

Abbiamo diviso liste in tre parti: a questo fa parte del primo elenco fino all'inizio della parte comune, b questo è parte del secondo elenco fino alla parte comune e c che è la parte comune di due elenchi. Contiamo le dimensioni delle liste e quindi la lista inversa b, questo causerà che quando avvieremo la lista di movimento da a fine termineremo allo reversedB (andremo a a -> firstElementOfC -> reversedB). Questo ci darà tre equazioni che ci permettono di ottenere la lunghezza della parte comune c.

Questo è troppo lento per la programmazione di competizioni o l'uso in produzione, ma penso che questo approccio sia interessante.

Answer 6

Forse irrilevante a questo punto, ma ecco il mio sporco approccio ricorsivo. Questo richiede tempo e O(M)O(M) spazio, dove M >= N per list_M di lunghezza M e list_N di lunghezza N

1. ricorsivamente iterare al fine di entrambi gli elenchi, quindi contati dalla fine del passo 2. Si noti che list_N colpirà null prima list_M, per M > N
2. stesse lunghezze M=N interseca quando list_M != list_N && list_M.next == list_N.next
3. diverse lunghezze M>N interseca quando list_N != null

Esempio di codice:

Node yListsHelper(Node n1, Node n2, Node result) { 
    if (n1 == null && n2 == null) 
     return null; 
    yLists(n1 == null ? n1 : n1.next, n2 == null ? n2 : n2.next, result); 
    if (n1 != null && n2 != null) { 
     if (n2.next == null) { // n1 > n2 
      result.next = n1; 
     } else if (n1.next == null) { // n1 < n2 
      result.next = n2; 
     } else if (n1 != n2 && n1.next == n2.next) { // n1 = n2 
      result.next = n1.next; // or n2.next 
     } 
    } 
    return result.next; 
}