如何在O（1）时间内将两个循环双链表合并在一起？

Question

我正在实现一个斐波那契堆，其中列表存储为循环双链表。我试图做的是给出一个指向一个链表中的随机节点的指针，另一个链表中的随机节点，我想在O（1）时间将它们合并在一起。我试图画出这个，但我似乎无法弄清楚如何做到这一点。这是我的第一个想法，在伪代码中:

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
}

每个 Node 有一个 left 和 right 属性，其分别将节点存储到左侧和右侧。然而，这并没有奏效。任何人都可以弄清楚如何将两个链表合并在一起？

Answer 1

不需要使用临时变量。请参阅下图和下面的关联伪代码。您要将灰色指针重新分配给其彩色对应项。你只需要小心指示的顺序。

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

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