كيفية دمج قائمتين دائريتين مرتبطتين بشكل مزدوج في زمن O(1)؟
-
29-09-2020 - |
سؤال
أقوم بتنفيذ كومة فيبوناتشي، حيث يتم تخزين القوائم كقوائم دائرية مرتبطة بشكل مزدوج.ما أحاول القيام به هو إعطاء مؤشر لعقدة عشوائية في قائمة مرتبطة واحدة، وعقدة عشوائية في قائمة أخرى، أريد دمجهما معًا في وقت 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
السمة، التي تخزن العقدة إلى اليسار واليمين، على التوالي.ومع ذلك، هذا لم ينجح.هل يمكن لأي شخص معرفة كيفية دمج قائمتين مرتبطتين معًا؟
المحلول
ليست هناك حاجة لاستخدام المتغيرات المؤقتة.انظر الصورة التالية والرمز الزائف المرتبط بها أدناه.تريد إعادة تعيين المؤشرات الرمادية إلى نظيرتها الملونة.عليك فقط أن تكون حذرا مع ترتيب التعليمات.
one.right.left = two.left; //red
two.left.right = one.right; //blue
one.right = two; //green
two.left = one; //purple
لا تنتمي إلى cs.stackexchange