Comment fusionner deux listes circulaires doublement liées en un temps O(1) ?

Question

J'implémente un tas de Fibonacci, où les listes sont stockées sous forme de listes circulaires à double lien.Ce que j'essaie de faire, c'est de donner un pointeur vers un nœud aléatoire dans une liste chaînée et un nœud aléatoire dans une autre, je veux les fusionner en un temps O(1).J'ai essayé de dessiner ça, mais je n'arrivais pas à comprendre comment faire ça.Voici ma première idée, en pseudocode :

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
}

Chaque Node a un left et right attribut, qui stocke le nœud à gauche et à droite, respectivement.Cependant, cela n'a pas fonctionné.Quelqu'un peut-il comprendre comment fusionner deux listes chaînées ?

Answer 1

Il n'est pas nécessaire d'utiliser des variables temporaires.Voir l'image suivante et le pseudocode associé ci-dessous.Vous souhaitez réaffecter les pointeurs gris à leur homologue coloré.Il faut juste faire attention à l'ordre des instructions.

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

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