Как объединить два круглых двусвязных списка за 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