Come unire insieme due elenchi circolari doppiamente collegati in O (1) Tempo?

Question

Sto implementazione di un heap fibonacci, in cui gli elenchi vengono memorizzati come elenchi circolari doppiamente collegati.Quello che sto cercando di fare viene dato un puntatore a un nodo casuale in un elenco collegato, e un nodo casuale in un altro, voglio unirli insieme in o (1) tempo.Ho provato a disegnarlo, ma non riuscivo a capire come farlo.Ecco la mia prima idea, in pseudocodice:

union(Node one, Node two) {
    if other = nil
        return

    p1 = one
    p2 = one.right
    p3 = two
    p4 = two.right

    p1.right = p4
    p4.left = p1
    p2.right = p3
    p3.left = p2
}

.

Ogni Node ha un attributo left e right, che memorizza il nodo a sinistra ea destra, rispettivamente.Tuttavia, questo non ha funzionato.Qualcuno può capire come unire insieme due elenchi collegati?

Answer 1

Non è necessario utilizzare variabili temporanee.Vedi la seguente immagine e la pseudocodice associata sottostante.Vuoi riassumere i puntatori grigi alla loro controparte colorata.Devi solo stare attento con l'ordine delle istruzioni.

one.right.left = two.left;  //red
two.left.right = one.right; //blue

one.right = two; //green
two.left = one;  //purple

.