I'm implementing a Fibonacci Heap, where the lists are stored as a circular doubly-linked lists. What I'm trying to do is given a pointer to a random node in one linked list, and a random node in another, I want to merge them together in O(1) time. I tried drawing this out, but I couldn't seem to figure out how to do this. Here is my first idea, in 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
}
Each Node
has a left
and right
attribute, which stores the node to the left and right, respectively. However, this didn't work. Can anyone figure out how to merge together two linked lists?