Como Se Fundem Dois Circular Duplamente Ligadas Listas Em O(1) O Tempo?

Question

Eu sou a implementação de um Heap de Fibonacci, onde as listas são armazenados como uma circular duplamente ligadas listas.O que eu estou tentando fazer é dado um ponteiro para um nó aleatório em uma lista ligada, e um nó aleatório em outro, quero intercalar-los juntos em O(1) hora.Eu tentei desenho isso, mas eu não conseguia descobrir como fazer isso.Aqui está a minha primeira idéia, em pseudocódigo:

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
}

Cada Node tem um left e right atributo que armazena o nó para a esquerda e para a direita, respectivamente.No entanto, isso não funciona.Alguém pode descobrir como unir-se duas listas ligadas?

Answer 1

Não há necessidade de usar variáveis temporárias.Veja a seguinte imagem associada e o pseudocódigo abaixo.Você deseja reatribuir o cinza ponteiros para seus coloridos de contrapartida.Você só tem que ter cuidado com a ordem das instruções.

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

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