Wie füge ich zwei kreisförmige doppelt verknüpfte Listen in O (1) -Zeit zusammen?

Question

Ich implementiere einen Fibonacci-Heap, in dem die Listen als zirkuläre doppelt verknüpfte Listen gespeichert sind.Ich versuche, einen Zeiger auf einen zufälligen Knoten in einer verknüpften Liste und einen zufälligen Knoten in einer anderen Liste zu geben. Ich möchte sie in O (1) -Zeit zusammenführen.Ich habe versucht, das herauszufinden, aber ich konnte anscheinend nicht herausfinden, wie das geht.Hier ist meine erste Idee im 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
}

Jeder Node hat eine left und right attribut, das den Knoten links bzw. rechts speichert.Dies hat jedoch nicht funktioniert.Kann jemand herausfinden, wie man zwei verknüpfte Listen zusammenführt?

Answer 1

Es ist nicht erforderlich, temporäre Variablen zu verwenden.Siehe das folgende Bild und den zugehörigen Pseudocode unten.Sie möchten die grauen Zeiger ihrem farbigen Gegenstück neu zuweisen.Sie müssen nur mit der Reihenfolge der Anweisungen vorsichtig sein.

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

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