Wie füge ich zwei kreisförmige doppelt verknüpfte Listen in O (1) -Zeit zusammen?
-
29-09-2020 - |
Frage
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?
Lösung
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