Intersection of Two Linked Lists
توجد قائمتان مترابطتان أحاديتا الاتجاه ضمن مجموعة واحدة من العقد. ترتبط العقدة i بالعقدة next[i]، وتنتهي القائمة عند -1. تبدأ القائمة A من العقدة headA، والقائمة B من العقدة headB. لا تُخزَّن العقد بترتيب معيّن، لذا اتبع الروابط.
قد تلتقي القائمتان: ابتداءً من عقدة ما، تتابعان عبر العقد نفسها حتى النهاية. أَعِد فهرس أول عقدة مشتركة بين القائمتين، أو -1 إذا لم تشتركا في أي عقدة.
الدالة
- nextinteger-array
- فهرس العقدة التي ترتبط بها كل عقدة، أو -1 للعقدة الأخيرة في القائمة
- headAinteger
- العقدة الأولى في القائمة A
- headBinteger
- العقدة الأولى في القائمة B
- تُرجعinteger
- العقدة الأولى المشتركة بين القائمتين، أو -1
القيود
2 ≤ n ≤ 104، حيث إنnهو طولnext.- كل
next[i]إما-1أو فهرس عقدة من0إلىn-1. 0 ≤ headA, headB ≤ n-1وheadA ≠ headB.- تنتهي كلتا القائمتين عند
-1من دون زيارة أي عقدة مرتين. لا توجد دورة. - كل عقدة موجودة في القائمة A، أو في القائمة B، أو في كلتيهما.
أمثلة
- المدخلات
- next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
- المخرجات
- 1
- الشرح
- تزور A العقد
3, 5, 1, 4, 0، وتزور B العقد2, 1, 4, 0. ابتداءً من العقدة1، يشتركان في كل عقدة، ولا توجد أي عقدة سابقة من A على B، لذا الإجابة هي1.
- المدخلات
- next = [2, 3, 4, -1, -1]headA = 0headB = 1
- المخرجات
- -1
- الشرح
- القائمة A هي
0, 2, 4والقائمة B هي1, 3. تنتهي كلتاهما عند-1دون الوصول إلى عقدة مشتركة، لذا تكون الإجابة-1.
- المدخلات
- next = [3, 2, 0, -1]headA = 1headB = 0
- المخرجات
- 0
- الشرح
- القائمة A هي
1, 2, 0, 3والقائمة B هي0, 3. القائمة B هي ذيل القائمة A، لذا فإن أول عقدة مشتركة هيheadBنفسها، أي العقدة0.
سؤال إضافي
هل يمكنك العثور على العقدة في زمن O(m + k) باستخدام ذاكرة إضافية O(1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
للعقدة رابط
nextواحد. بعد أن تصل القائمتان إلى العقدة نفسها، هل يمكن أن تنفصلا مجددًا؟ ماذا يخبرك ذلك عن شكل القائمتين؟لو كان للقائمتين الطول نفسه، لأمكنك السير فيهما جنبًا إلى جنب والتوقف عندما يقف المؤشران عند العقدة نفسها. تكمن المشكلة في العقد الإضافية في بداية القائمة الأطول. كيف يمكن للمؤشرين أن يقطعا المسافة الإجمالية نفسها؟
حرّك المؤشر
aعلى طول القائمة A، وعندما يتجاوز نهايتها، أعد تشغيله عندheadB. افعل الشيء نفسه معb، وأعد تشغيله عندheadA. توقّف عندما يصبحa == b. تلك العقدة، أو-1، هي الإجابة.
الحل
للعقدة next واحد، لذا فإن قائمتين تلتقيان لا تنفصلان مجددًا. تُشكّلان Y، بدايتين منفصلتين تلتقيان عند ذيل مشترك، والإجابة هي نقطة الالتقاء. قد يختلف طول البدايتين، لذا فإن تحريك القائمتين معًا يفوّت نقطة الالتقاء. أدناه، m وk هما طولا A وB.
تحقّق من كل عقدة في A مقابل جميع العقد في B
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
المؤشر هو فهرس عقدة، والتحرك إلى الأمام يكون باستخدام node = next[node]. لكل عقدة a في A بالترتيب، مرّ على جميع عقد B وقارن كل عقدة بـ a. أول a تطابق هي الإجابة، لأن كل عقدة سابقة في A لم تطابق. يُعاد فحص B لكل عقدة في A: مع وجود 5000 عقدة في كل قائمة وعدم وجود عقدة مشتركة، يكون ذلك 2.5 × 10^7 مقارنة.
الخوارزمية
- عيّن
a = headA. - ما دام
aلا يساوي-1، تحرّك بـbمنheadBإلى-1. - إذا كان
b == aفي أي وقت، فأعِدa. - وإلا، حرّك
a = next[a]وكرّر. - إذا نفدت عناصر القائمة A، فأعِد
-1.
def getIntersectionNode(next, headA, headB):
a = headA
while a != -1:
# Is node a also on list B? Walk all of B to find out.
b = headB
while b != -1:
if a == b:
return a
b = next[b]
a = next[a]
return -1علِّم عُقد القائمة B
الفكرة
أجب عن السؤال «هل هذه العقدة موجودة في B؟» مرةً لكل عقدة: تجوّل في B وضع علامة على كل عقدة في مصفوفة منطقية حجمها n. ففهارس العقد أعداد صحيحة صغيرة، لذا تكفي مصفوفة بدلًا من مجموعة تجزئة. ثم تجوّل في A بدءًا من رأسها. أول عقدة عليها علامة موجودة في كلتا القائمتين، وهي أول عقدة من هذا النوع لأنك تتجوّل في A بالترتيب. في المثال الأول، يضع B علامات على 2, 1, 4, 0، ويمرّ التجوّل على طول A بالعقدتين 3 و5 قبل أن يتوقف عند 1. يُتجوّل في كل قائمة مرة واحدة، لذا فالزمن هو O(m + k)، مقابل استخدام n علامة.
الخوارزمية
- أنشئ المصفوفة
onB، التي تحتوي علىnقيم منطقية مضبوطة على false. - تتبّع القائمة B بدءًا من
headBواضبطonB[node] = trueلكل عقدة. - تتبّع القائمة A بدءًا من
headA. أعد أول عقدة تكون فيهاonB[node]true. - إذا انتهت القائمة A، فأعد
-1.
def getIntersectionNode(next, headA, headB):
# Mark every node of list B.
on_b = [False] * len(next)
node = headB
while node != -1:
on_b[node] = True
node = next[node]
# The first marked node on list A is the meeting point.
node = headA
while node != -1:
if on_b[node]:
return node
node = next[node]
return -1مؤشّران ينتقلان بين القوائم
الفكرة
قسّم كل قائمة عند نقطة الالتقاء: تحتوي A على x عقد خاصة ثم c عقد مشتركة، وتحتوي B على y عقد خاصة ثم العقد المشتركة نفسها وعددها c. يتحرك المؤشر a عبر A، ويخطو إلى -1، ثم يبدأ من جديد عند headB، ويصل إلى نقطة الالتقاء للمرة الثانية بعد x + c + 1 + y خطوة. يتحرك المؤشر b عبر B ثم A، ويصل بعد y + c + 1 + x خطوة. يتساوى المجموعان. في المثال الأول x = 2، وy = 1، وc = 3، ويقف كلاهما عند العقدة 1 بعد سبع خطوات.
إذا لم يكن هناك ذيل مشترك، يقف كلا المؤشرين عند -1 بعد m + 1 + k خطوة (أو بعد m عندما يكون m = k)، وتُرجع الحلقة -1. وهذا التوقف المشترك هو سبب تخطي كل مؤشر للعقدة -1 قبل أن ينتقل. يتحرك كل مؤشر بحد أقصى m + k + 1 مرة، مع استخدام ذاكرة لمؤشرين.
الخوارزمية
- عيّن
a = headAوb = headB. - ما دام
a != b: حرّكaإلىheadBإذا كانت قيمته-1، وإلا فإلىnext[a]. - في الجولة نفسها، حرّك
bإلىheadAإذا كانت قيمته-1، وإلا فإلىnext[b]. - عندما تنتهي الحلقة، أعد
a. فهو أول عقدة مشتركة، أو-1.
def getIntersectionNode(next, headA, headB):
a, b = headA, headB
# Each pointer walks its own list, then the other one. Both cover
# the same number of nodes, so they reach the meeting node together,
# or reach -1 together when there is none.
while a != b:
a = headB if a == -1 else next[a]
b = headA if b == -1 else next[b]
return a
أخطاء شائعة وحالات حدّية
- الانتقال من العقدة الأخيرة مباشرةً إلى الرأس الآخر، متجاوزًا التوقف عند
-1. عندما لا تتشارك القائمتان أي عقدة، لا تحمل المؤشرات القيمة نفسها أبدًا، وتستمر الحلقة إلى الأبد. - إعادة مؤشر إلى رأس قائمته. عندها يجتاز كل مؤشر قائمته الخاصة، ولا يلتقيان إلا عندما تتطابق دوراتهما، وقد يستغرق ذلك ما يصل إلى
(m + 1)·(k + 1)حركة. - اعتبار ترتيب المصفوفة ترتيبًا للقائمة. لا تكون العقدة
0رأسًا إلا إذا دلّheadAأوheadBعلى ذلك، والعناصر المتجاورة في المصفوفة ليست بالضرورة متجاورة في القائمة. - في Lua وR، لا تنسَ أن المصفوفات تبدأ من 1. أبقِ فهارس العقد تبدأ من 0، واقرأ
next[node + 1].
أسئلة شائعة3
كيف تجد الموضع الذي تتقاطع فيه قائمتان مترابطتان دون استخدام ذاكرة إضافية؟
استخدم مؤشّرين. يسير كلٌّ منهما في قائمته الخاصة، وبعد تجاوز نهايتها، يواصل السير بدءًا من رأس القائمة الأخرى. يقطع كلاهما المسافة الإجمالية نفسها، لذا يصلان إلى أول عقدة مشتركة في اللحظة نفسها، أو إلى النهاية معًا إذا لم توجد عقدة مشتركة.
هل يمكنك إيجاد التقاطع من خلال مقارنة أطوال القوائم؟
نعم. احسب عدد العُقد في كلتا القائمتين، وحرّك المؤشر في القائمة الأطول إلى الأمام بمقدار الفرق، ثم حرّك كليهما خطوة واحدة في كل مرة حتى يتساويا. يستغرق هذا أيضًا زمنًا قدره O(m + k) ويستهلك ذاكرة قدرها O(1)؛ وتحقق طريقة التبديل المحاذاة نفسها دون إجراء عمليتي العد.
ما هو التعقيد الزمني لإيجاد تقاطع قائمتين مترابطتين؟
تعمل طريقتا المؤشرين والطول في زمن O(m + k) وباستخدام ذاكرة إضافية مقدارها O(1). تذكُّر إحدى القائمتين في مجموعة أو مصفوفة علامات خطيّ أيضًا، لكنه يحتاج إلى ذاكرة لتلك القائمة. تستغرق مقارنة كل زوج من العُقد O(m·k).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def getIntersectionNode(next, headA, headB):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
next = [-1, 4, 1, 5, 0, 1] headA = 3 headB = 2
الإخراج المتوقع
1