Middle of the Linked List
لديك قائمة مترابطة أحادية مخزنة في مصفوفتين بالطول نفسه. تحتوي العقدة i على القيمة values[i] وترتبط بالعقدة next[i]، وتنهي -1 القائمة، والرأس هو العقدة 0. العقد غير مخزنة بترتيب القائمة، لذا اتبع الروابط.
أعِد قيمة العقدة الوسطى. عندما تحتوي القائمة على عدد زوجي من العقد، تكون هناك عقدتان وسطيتان؛ أَعِد قيمة الثانية.
الدالة
- valuesinteger-array
- القيمة التي تحتفظ بها كل عقدة
- nextinteger-array
- فهرس العقدة التي ترتبط بها كل عقدة، أو -1 للعقدة الأخيرة
- تُرجعinteger
- قيمة العقدة الوسطى، أي العقدة الوسطى الثانية عندما يكون الطول زوجيًا
القيود
1 ≤ n ≤ 5000، حيث إنnهو طول كلٍّ منvaluesوnext.-104 ≤ values[i] ≤ 104- كل
next[i]يساوي-1أو فهرس عقدة من0إلىn-1. - بدءًا من العقدة
0، تزور القائمة كل عقدة مرة واحدة بالضبط، ثم تصل إلى-1. لا توجد دورة.
أمثلة
- المدخلات
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- المخرجات
- 5
- الشرح
- يعطي تتبّع الروابط من العقدة
0العقد0, 3, 4, 2, 1، لذا تكون القائمة4, 7, 5, 2, 9. العقدة الثالثة من أصل خمس هي العقدة4، وقيمتها5. أما العنصر الأوسط في المصفوفة نفسها،values[2] = 2، فهو عقدة مختلفة.
- المدخلات
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- المخرجات
- 40
- الشرح
- هنا تُخزَّن العقد بالترتيب. عندما يكون عدد العقد ستًا، توجد عقدتان في المنتصف،
30و40، وتكون الثانية هي الفائزة.
- المدخلات
- values = [8]next = [-1]
- المخرجات
- 8
- الشرح
- القائمة التي تحتوي على عقدة واحدة يكون وسطها هو تلك العقدة نفسها.
+13 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك إرجاع العقدة التي تقع عند ثلث طول القائمة في مرور واحد؟ ما سرعة تحرك كل مؤشر، وأين ستتوقف؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
أنت لا تعرف طول القائمة حتى تصل إلى نهايتها. ماذا لو بدأ متجوّلان من رأسها وكان أحدهما يتحرك بسرعة ضعف سرعة الآخر؟
عندما يصل المتحرك الأسرع إلى النهاية، يكون المتحرك الأبطأ قد قطع نصف المسافة، لذا يقف عند العقدة الوسطى. والتفصيل الوحيد المتبقي هو تحديد وقت التوقف بحيث تقع القائمة ذات الطول الزوجي عند العقدة الوسطى الثانية.
ابدأ
slowوfastعند العقدة0. ما دامfastلا يساوي-1وnext[fast]لا يساوي-1، حرّكslowرابطًا واحدًا وfastرابطين. ثم أعدvalues[slow].
الحل
في المصفوفة، يقع المنتصف عند الفهرس n / 2. لا تمنحك القائمة المرتبطة فهرسًا: لا تعرف طولها إلا بالسير حتى نهايتها، وعندها تكون قد تجاوزت المنتصف. يمكنك نسخ القائمة إلى مصفوفة، أو عدّ عناصرها أولًا ثم السير فيها مرة أخرى. أما الحل الأنيق فيرسل مؤشرين عبر القائمة بسرعتين مختلفتين، بحيث يكون المؤشر البطيء في المنتصف عندما يصل السريع إلى النهاية.
انسخ القيم إلى مصفوفة
الفكرة
في هذه المسألة، المؤشر هو فهرس العقدة. الانتقال إلى العقدة التالية يتم عبر node = next[node]، والوصول إلى -1 يعني أنك تجاوزت نهاية القائمة. في المثال الأول، ينتقل المسار من العقدة 0 هكذا: 0 → 3 → 4 → 2 → 1 → -1.
تكمن مشكلة القائمة في أنك لا تستطيع القفز إلى موضع محدد فيها. لذا حوّلها إلى شيء يمكنك ذلك فيه: مرّ على القائمة مرة واحدة، وأضف كل قيمة إلى مصفوفة جديدة عند المرور بها. تحتوي تلك المصفوفة على القيم بترتيب القائمة، أي [4, 7, 5, 2, 9] في المثال الأول، ويكون عنصرها الأوسط عند الفهرس length / 2 باستخدام القسمة الصحيحة.
يعطيك هذا الفهرس العنصر الأوسط الثاني تلقائيًا عندما يكون الطول زوجيًا: ست قيم تعطي الفهرس 3، أي القيمة الرابعة، وهي 40 في المثال الثاني. يستغرق المرور زمنًا قدره O(n)، وتتطلب عملية النسخ ذاكرة إضافية قدرها O(n)، وهو ما تتجنبه الطريقتان التاليتان.
الخوارزمية
- ابدأ بمصفوفة فارغة و
node = 0. - طالما أن
nodeلا يساوي-1، أضفvalues[node]وانتقل إلىnext[node]. - أعِد العنصر عند الفهرس
length / 2بعد التقريب إلى الأسفل.
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]عُدّ، ثم امشِ نصف المسافة
الفكرة
لا تحتاج إلى النسخة كاملة، بل إلى الطول فقط. مرّ على القائمة مرة واحدة وعدّ العُقد. ثم ابدأ من جديد عند الرأس وخذ length / 2 خطوة، مع التقريب إلى الأسفل. العقدة التي تتوقف عندها هي العقدة الوسطى.
لماذا هذا العدد من الخطوات: بعد k خطوات، تكون عند العقدة في الموضع k، مع احتساب الرأس في الموضع 0. تقع العقدة الوسطى في قائمة طولها 5 عند الموضع 2، وتقع العقدة الوسطى الثانية في قائمة طولها 6 عند الموضع 3، وكلاهما length / 2. في المثال الأول، تعدّ 5، وتأخذ خطوتين 0 → 3 → 4، ثم تقرأ values[4] = 5.
أصبحت الذاكرة الآن O(1). والتكلفة هي المرور على نصف القائمة مرة ثانية، أي 1.5n حركة إجمالًا، وهو ما يزال O(n).
الخوارزمية
- انتقل من العقدة
0إلى-1وعدّ العقد. - عُد إلى العقدة
0. - نفّذ
node = next[node]تمامًاcount / 2مرة، مع التقريب إلى الأسفل. - أعِد
values[node].
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]المؤشرات السريعة والبطيئة
الفكرة
ضع مؤشرين عند الرأس. في كل دورة، يتحرك slow عقدة واحدة، ويتحرك fast عقدتين. بعد k دورات، يكون slow عند الموضع k وfast عند الموضع 2k، لذا يكون slow قد قطع دائمًا نصف المسافة التي قطعها fast. عندما يصل fast إلى النهاية، يكون slow في المنتصف، ولم تكن بحاجة إلى معرفة الطول.
تحدد قاعدة التوقف أيّ المنتصفين ستحصل عليه. تابع ما دام fast عقدة فعلية ولديه عقدة تليه: fast != -1 وnext[fast] != -1. إذا كان الطول فرديًا، يتوقف fast عند العقدة الأخيرة. وإذا كان الطول زوجيًا، يتجاوز fast النهاية إلى -1، ما يدفع slow خطوة إضافية إلى المنتصف الثاني. في المثال الثاني، يتحرك slow عبر 0, 1, 2, 3 بينما يتحرك fast عبر 0, 2, 4, -1، وتكون values[3] مساويةً لـ40.
في المثال الأول، يزور slow العقد 0, 3, 4 بينما يزور fast العقد 0, 4, 1؛ والعقدة 1 هي الأخيرة، لذا تتوقف الحلقة وslow عند العقدة 4، وتكون الإجابة 5. ينفذ fast نحو n حركات، وينفذ slow n / 2 حركة، في مرور واحد وباستخدام عددين صحيحين من الذاكرة.
الخوارزمية
- عيّن
slow = 0وfast = 0. - ما دام
fast != -1وnext[fast] != -1، عيّنslow = next[slow]وfast = next[next[fast]]. - أعِد
values[slow].
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
أخطاء شائعة وحالات حدّية
الحلقة قصيرة، لذا تكمن الأخطاء في نقطة بدايتها ونقطة توقفها وما تُعيده.
- إعادة
values[n / 2]. العقد غير مخزنة بترتيب القائمة، لذا يكون العنصر الأوسط في المصفوفة عادةً عقدة أخرى. في المثال الأول، تعطي2بدلًا من5. - الحصول على العنصر الأوسط الأول عندما يكون الطول زوجيًا. تتوقف الحلقة التي تستمر ما دامت كل من
next[fast]وnext[next[fast]]تشير إلى عقدة موجودة، قبل الأوان بجولة واحدة، وتُعيد30بدلًا من40في المثال الثاني. - التحقق من
next[fast]قبلfast != -1. عندما يكون الطول زوجيًا، تصبح قيمة fast هي-1، وتؤدي قراءةnext[-1]إلى تعطّل البرنامج في معظم اللغات. في Python، تُقرأ آخر خانة بصمت بدلًا من ذلك، وهذا أسوأ. - الانتقال
count / 2 - 1خطوة أو التقريب إلى الأعلى في أسلوب العد. اعتبر الرأس في الموضع0وخذcount / 2خطوة بالضبط، مع التقريب إلى الأسفل. - إعادة فهرس العقدة بدلًا من قيمتها.
- نسيان الإزاحة في Lua وR، حيث تبدأ المصفوفات من 1. أبقِ فهارس العقد صفرية الأساس واقرأ
next[node + 1]. تحجز Ruby وR الكلمةnext، لذا تسمّي الحلول الأولية فيهما المعاملnext_.
أسئلة شائعة4
لماذا يعثر المؤشران السريع والبطيء على منتصف قائمة مرتبطة؟
يبدأ كلاهما من الرأس، وفي كل دورة يتحرك المؤشر السريع عقدتين بينما يتحرك المؤشر البطيء عقدة واحدة. بعد k دورات، يكون المؤشر السريع عند الموضع 2k والبطيء عند الموضع k، أي إنه قطع نصف المسافة تمامًا. لذا، عندما يصل المؤشر السريع إلى نهاية القائمة، يكون المؤشر البطيء في منتصفها.
ما التعقيد الزمني وتعقيد المساحة لإيجاد منتصف قائمة مرتبطة؟
تستغرق الأساليب الثلاثة كلها زمنًا قدره O(n)، إذ لا يمكن العثور على العنصر الأوسط دون اجتياز نحو نصف القائمة أو أكثر. يتطلب نسخ القيم ذاكرة إضافية قدرها O(n). أما العد أولًا ومؤشرا السرعة والبطء، فيستخدم كل منها O(1)، ولا يحتاج المؤشران إلا إلى اجتياز واحد.
كيف تُرجِع العقدة الوسطى الأولى بدلًا من الثانية؟
غيّر شرط التوقف بحيث يتوقف المؤشر السريع قبل دورة واحدة: كرّر ما دام next[fast] != -1 وnext[next[fast]] != -1. عند وجود ست عقد، يتوقف المؤشر البطيء عند الموضع 2 بدلًا من 3. في طريقة العد، تحرّك (count - 1) / 2 خطوات بدلًا من count / 2.
أين تُستخدم تقنية المؤشر السريع والمؤشر البطيء أيضًا؟
تكتشف السرعتان نفسيهما وجود دورة في قائمة مرتبطة: ففي الحلقة، يتجاوز المؤشر السريع المؤشر البطيء ويلتقيان. كما يعثران على موضع بداية الدورة، ويقسمان القائمة إلى نصفين للترتيب بالدمج أو للتحقق مما إذا كانت القائمة تُقرأ بالطريقة نفسها في كلا الاتجاهين.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def middleNode(values, next):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
المتوقع
5