0
$\begingroup$

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?

Improve this question
$\endgroup$
2
$\begingroup$

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.

doubly linked list merge

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

one.right = two; //green
two.left = one;  //purple
Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – nishantc1527 Apr 11 '20 at 2:26
  • $\begingroup$ 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. $\endgroup$ – Steven Apr 11 '20 at 2:30
  • $\begingroup$ Oh, I understand. Thanks! $\endgroup$ – nishantc1527 Apr 11 '20 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.