How To Merge Together Two Circular Doubly-Linked Lists In O(1) Time?

Question

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?

Answer 1

There is no need to use temporary variables. See the following picture and the associated pseudocode below. You want to reassign the gray pointers to their colored counterpart. You just have to be careful with the order of the instructions.

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

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