¿Cómo fusionar juntos dos listas circulares vinculadas en O (1) tiempo?

Question

Estoy implementando un montón de Fibonacci, donde las listas se almacenan como una lista circularmente vinculada.Lo que estoy tratando de hacer recibe un puntero a un nodo aleatorio en una lista vinculada, y un nodo aleatorio en otro, quiero fusionarlos juntos en O (1) tiempo.Intenté sacar esto, pero no pude averiguar cómo hacer esto.Aquí está mi primera idea, en 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 tiene un atributo left y right, que almacena el nodo hacia la izquierda y hacia la derecha, respectivamente.Sin embargo, esto no funcionó.¿Alguien puede averiguar cómo combinar dos listas enlazadas?

Answer 1

No hay necesidad de usar variables temporales.Vea la siguiente imagen y el pseudocodo asociado a continuación.Quieres reasignar los punteros grises a su contraparte de color.Solo tienes que tener cuidado con el orden de las instrucciones.

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

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