كيفية دمج قائمتين دائريتين مرتبطتين بشكل مزدوج في زمن 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