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

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?

## 1 Answer

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

• Will this still work if you're given two random nodes instead of the first ones? For example, if you're given the 2nd node in the first linked list and the third node in the second? Thanks for you're answer and diagram. – nishantc1527 Apr 11 '20 at 2:26
• The structure of each list is completely symmetric w.r.t. rotations. There is no "first" node. It will work for any choice of a node from the first list and a node from the second list. I've just chosen to draw the given nodes as the leftmost ones in the picture. – Steven Apr 11 '20 at 2:30
• Oh, I understand. Thanks! – nishantc1527 Apr 11 '20 at 3:52