o（1）時に2つの循環二重リンクリストを一緒にマージする方法？

Question

Listsが循環二重リンクリストとして格納されているFibonaccciヒープを実装しています。私がしようとしていることは、1つのリンクリスト内のランダムなノードへのポインタと、他のものにランダムなノードを与えられます、私は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属性があります。しかし、これはうまくいきませんでした。2つのリンクリストをマージする方法を理解することができますか？

Answer 1

一時変数を使用する必要はありません。以下の写真と関連する疑似コードを参照してください。あなたは灰色のポインタを彼らの色のカウンターパートに再割り当てしたいです。指示の順序に注意しなければならないだけです。

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

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

.