Remove Nth Node From End of List
لديك قائمة مرتبطة أحادية مخزنة في مصفوفتين لهما الطول نفسه. تحتوي العقدة i على القيمة values[i] وترتبط بالعقدة next[i]، وتشير -1 إلى نهاية القائمة، والعقدة 0 هي الرأس. لا تُخزَّن العقد بترتيب القائمة، لذا اتبع الروابط.
أزل العقدة رقم n عند العد من نهاية القائمة، حيث تكون العقدة الأخيرة هي الأولى من النهاية. أعد قيم العقد المتبقية بترتيب القائمة.
الدالة
- valuesinteger-array
- القيمة التي تحتفظ بها كل عقدة
- nextinteger-array
- فهرس العقدة التي ترتبط بها كل عقدة، أو -1 للعقدة الأخيرة
- ninteger
- أيُّ عقدة يجب إزالتها، عند العدّ من النهاية، حيث إن 1 هي العقدة الأخيرة
- تُرجعinteger-array
- القيم المتبقية بترتيب القائمة، وتكون فارغة عند إزالة العقدة الوحيدة
القيود
1 ≤ L ≤ 5000، حيث إنLهو طول كلٍّ منvaluesوnext.-100 ≤ values[i] ≤ 1001 ≤ n ≤ L- كل عنصر من
next[i]إما-1أو فهرس عقدة من0إلىL-1. - بدءًا من العقدة
0، تمرّ القائمة بكل عقدة مرة واحدة بالضبط، ثم تصل إلى-1. لا توجد دورة.
أمثلة
- المدخلات
- values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
- المخرجات
- [5, 2, 6, 7]
- الشرح
- باتباع الروابط بدءًا من العقدة
0، نزور العقد0, 2, 4, 1, 3، لذا تُقرأ القائمة5, 2, 6, 9, 7. العقدة الثانية من النهاية هي العقدة1، وقيمتها9، ومن دونها تُقرأ القائمة5, 2, 6, 7. مُدخل المصفوفةvalues[5-2] = 7هو العقدة الأخيرة، وليس العقدة التي يجب حذفها.
- المدخلات
- values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
- المخرجات
- [20, 30, 40]
- الشرح
- أربع عقد و
n = 4: العقدة الرابعة من النهاية هي الرأس. تبدأ القائمة الآن عند العقدة1وتُقرأ20, 30, 40.
- المدخلات
- values = [42]next = [-1]n = 1
- المخرجات
- []
- الشرح
- العقدة الوحيدة هي الرأس والعقدة الأخيرة في الوقت نفسه. تؤدي إزالتها إلى قائمة فارغة، لذا تكون الإجابة
[].
+14 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك العثور على العقدة وفصلها في مرور واحد، دون حساب الطول أولًا؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تسير القائمة إلى الأمام فقط، وتُحدَّد العقدة بحسب بُعدها عن النهاية. إذا كنت تعرف الطول
L، ففي أي موضع من البداية ستكون؟ ورابط أي عقدة عليك تغييره لإزالتها؟يمكنك قياس المسافة إلى النهاية دون معرفة الطول. ابدأ بمؤشر يسبق مؤشرًا آخر بمقدار
nروابط، ثم حرّكهما معًا. عندما يصل المؤشر المتقدم إلى العقدة الأخيرة، يكون المؤشر التالي واقفًا مباشرةً قبل العقدة المراد حذفها.حرّك
fastإلى الأمامnمرات. إذا أصبح الآن-1، فإن الرأس هو العقدة المراد حذفها، لذا تبدأ القائمة عندnext[0]. وإلا، حرّكslowوfastمعًا ما دامnext[fast] != -1، ثم عيّنnext[slow] = next[next[slow]]. تجوّل في القائمة بدءًا من الرأس واجمع القيم.
الحل
يُحدَّد الهدف بمسافته من النهاية، لكن القائمة المرتبطة أحادية الاتجاه لا تتيح لك سوى التقدّم، ولا تعرف أين تقع النهاية إلا عندما تصل إليها. كما أن إزالة عقدة تعني الوقوف عند العقدة التي تسبقها، لأن رابط تلك العقدة هو الذي يتغيّر. يمكنك نسخ القائمة إلى مصفوفة، أو حساب عدد عناصرها ثم المرور عليها مرة أخرى. والحل التقليدي هو إبقاء مؤشّرين بينهما n روابط، بحيث يقف المؤشّر الخلفي مباشرةً قبل الهدف عندما يصل المؤشّر الأمامي إلى العقدة الأخيرة. أدناه، L هو عدد العقد.
انسخ القيم إلى مصفوفة
الفكرة
في هذه المسألة، المؤشر هو فهرس عقدة. الانتقال إلى الأمام يكون عبر node = next[node]، والوصول إلى -1 يعني أنك تجاوزت نهاية القائمة. في المثال الأول، ينتقل المسار من العقدة 0 هكذا: 0 → 2 → 4 → 1 → 3 → -1.
يكون العد من النهاية صعبًا فقط لأن القائمة لا تملك مواضع. لذا أضف إليها مواضع: مرّ عليها مرة واحدة وألحِق كل قيمة بمصفوفة. في المثال الأول، تكون هذه المصفوفة [5, 2, 6, 9, 7]. في مصفوفة تضم L قيمة، تقع القيمة الأخيرة عند الفهرس L-1، لذا تقع القيمة رقم n من النهاية عند الفهرس L-n. هنا، يكون ذلك 5-2 = 3، أي القيمة 9. احذفها وأعِد [5, 2, 6, 7].
هذا صحيح ويعمل بزمن O(L)، لكنه ينسخ القائمة بأكملها ولا يغيّر أي رابط. الهدف من المسألة هو تعديل القائمة نفسها باستخدام ذاكرة إضافية مقدارها O(1)، وهذا ما يفعله النهجان التاليان.
الخوارزمية
- ابدأ بمصفوفة فارغة و
node = 0. - ما دام
nodeلا يساوي-1، فأضفvalues[node]وانتقل إلىnext[node]. - احذف العنصر عند الفهرس
length - n. - أعِد المصفوفة.
def removeNthFromEnd(values, next, n):
# Write the values out in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Counting from the end, the n-th value sits at index len(order) - n.
del order[len(order) - n]
return orderعُدَّ العُقَد، ثم أزل الروابط
الفكرة
لإزالة عقدة من قائمة، غيّر رابط العقدة التي تسبقها بحيث يتخطاها: next[prev] = next[next[prev]]. تظل العقدة المُزالة موجودة في المصفوفات، لكن لا يصل إليها أي اجتياز يبدأ من الرأس مرة أخرى.
إذًا، ابحث عن prev. عُدّ العقد في اجتياز أول. باعتبار الرأس في الموضع 0، تقع العقدة المستهدفة في الموضع L-n، والعقدة التي تسبقها في الموضع L-n-1، ويمكن الوصول إليها من الرأس في L-n-1 خطوة. في المثال الأول، L = 5 وn = 2: توصلك خطوتان 0 → 2 → 4 إلى العقدة 4، التي ترتبط بالعقدة 1، وهي 9. إن ضبط next[4] = next[1] = 3 يجعل القائمة تُقرأ على النحو التالي: 5, 2, 6, 7.
هناك حالة لا توجد فيها عقدة تسبق العقدة المستهدفة: n = L، عندما تكون العقدة المستهدفة هي الرأس. عندها لا حاجة إلى إعادة ربط أي شيء. تبدأ القائمة من next[0] بدلًا من 0، كما في المثال الثاني. بعد ذلك، اجتز القائمة من الرأس لجمع الإجابة. يستغرق اجتياز القائمة مرتين نحو 2L حركة، والذاكرة الإضافية بخلاف مساحة الإجابة لا تتجاوز بضعة أعداد صحيحة.
الخوارزمية
- انتقل من العقدة
0إلى-1وعدّ العقد لتحديدL. - إذا كان
n == L، فسيكون الرأس الجديد هوnext[0]. - بخلاف ذلك، ابدأ
prevعند العقدة0وحرّكهL-n-1مرات، ثم عيّنnext[prev] = next[next[prev]]. - انتقل انطلاقًا من الرأس واجمع
values[node]بالترتيب.
def removeNthFromEnd(values, next, n):
# First pass: count the nodes.
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
head = 0
if n == length:
# The node to remove is the head, so the list starts at its second node.
head = next[0]
else:
# Second pass: stop on the node just before position length - n.
prev = 0
for _ in range(length - n - 1):
prev = next[prev]
next[prev] = next[next[prev]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return resultمؤشران يفصل بينهما n رابطًا
الفكرة
يمكنك قياس «n من النهاية» من دون معرفة L. حرّك fast إلى الأمام بمقدار n روابط، بينما ينتظر slow عند الرأس. ثم حرّكهما معًا رابطًا واحدًا في كل مرة. تبقى المسافة بينهما n، لذا عندما يقف fast عند العقدة الأخيرة (next[fast] == -1، الموضع L-1)، يقف slow عند الموضع L-1-n: العقدة التي تسبق الهدف مباشرةً. تؤدي عملية next[slow] = next[next[slow]] واحدة إلى استبعاد الهدف.
تابع المثال الأول. يخطو fast خطوتين: 0 → 2 → 4. والآن يتحرك الاثنان: يصل slow إلى 2 بينما يصل fast إلى 1، ثم يصل slow إلى 4 بينما يصل fast إلى 3. العقدة 3 هي الأخيرة، لذا تتوقف. next[4] هي العقدة 1، وقيمتها 9، وتعيين next[4] = next[1] = 3 يزيلها.
تظهر حالة الرأس تلقائيًا. بما أن n ≤ L، لا يصل fast إلى -1 أثناء انطلاقه من الرأس إلا عندما n = L، وهذا بالضبط ما يحدث عندما يكون الرأس هو الهدف. عند استخدام كائنات العقد، يمكنك وضع عقدة وهمية أمام الرأس لإلغاء هذه الحالة؛ وهنا يؤدي التحقق fast == -1 الغرض نفسه. يستغرق العثور على العقدة وفك ارتباطها مرورًا واحدًا. أما كتابة الإجابة فتتطلب اجتيازًا إضافيًا، وهو ما تحتاج إليه كل الطرق.
الخوارزمية
- عيّن
fast = 0وحرّكهnمرات باستخدامfast = next[fast]. - إذا كان
fast == -1، فالعقدة الرأس هي الهدف: الرأس الجديد هوnext[0]. - وإلا، عيّن
slow = 0وحرّكهما معًا ما دامnext[fast] != -1. - عيّن
next[slow] = next[next[slow]]. - ابدأ من الرأس واجمع
values[node]بالترتيب.
def removeNthFromEnd(values, next, n):
# Send fast n links ahead of slow.
fast = 0
for _ in range(n):
fast = next[fast]
head = 0
if fast == -1:
# Fast fell off the end, so the list has exactly n nodes: remove the head.
head = next[0]
else:
# Move both, keeping the gap. When fast stands on the last node,
# slow stands just before the node to remove.
slow = 0
while next[fast] != -1:
slow = next[slow]
fast = next[fast]
next[slow] = next[next[slow]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
أخطاء شائعة وحالات حدّية
تأتي معظم الإجابات الخاطئة من الموضع الذي يتوقف عنده المؤشر التابع، ومن الحالة التي يُحذف فيها الرأس.
- حذف العنصر عند فهرس المصفوفة
L-n. لا تُخزَّن العقد بترتيب القائمة، لذا يكون هذا الفهرس عادةً عقدةً أخرى. في المثال الأول،values[3] = 7هي العقدة الأخيرة، وليست9. - التوقف عندما تكون
fast == -1بدلًا من التوقف عندما تكونnext[fast] == -1. يؤدي ذلك إلى تحريكslowخطوةً إضافية، ليصل إلى العقدة المستهدفة نفسها، وفي القائمة المرتبطة أحادية الاتجاه لا يمكنك فصل عقدة عن العقدة نفسها. - نسيان حالة الرأس. عندما تكون
n = L، تصبح قيمةfastهي-1بعد بدء تحريكه من الرأس، وتؤدي قراءةnext[fast]إلى حدوث خطأ في معظم اللغات. تقرأ Python القيمةnext[-1]دون اعتراض، وتُرجع قائمة خاطئة، ما يجعل اكتشاف الخطأ أصعب. - فصل العقدة باستخدام
next[slow] = next[slow] + 1أوslow + 2. العقد المتجاورة في القائمة ليست متجاورة في المصفوفات؛ والطريقة الوحيدة للوصول إلى العقدة التي تلي العقدة المستهدفة هيnext[next[slow]]. - جمع الإجابة بدءًا من العقدة
0بعد حذف الرأس. ابدأ المرور الأخير من الرأس الجديد. - نسيان الإزاحة في Lua وR، حيث تبدأ المصفوفات من 1. أبقِ فهارس العقد مبنية على الصفر، واقرأ
next[node + 1]. تحجز Ruby وR الكلمةnext، لذا تسمّي الشيفرات التمهيدية فيهما المَعلمةnext_.
أسئلة شائعة4
كيف تحذف العقدة رقم n من نهاية قائمة مترابطة بمرور واحد؟
استخدم مؤشرين بينهما فجوة مقدارها n. حرّك المؤشر الأول إلى الأمام بمقدار n عقد، ثم حرّكهما معًا حتى يصل المؤشر الأول إلى العقدة الأخيرة. عندها يكون المؤشر الثاني قبل العقدة المراد حذفها مباشرةً، لذا وجّه رابطها ليتجاوز تلك العقدة. إذا تجاوز المؤشر الأول نهاية القائمة أثناء تقدّمه المسبق، فالعقدة المراد حذفها هي الرأس.
لماذا تستخدم حلول هذه المسألة عقدةً وهمية؟
تعني إزالة عقدة تغيير الرابط في العقدة التي تسبقها، ولا تسبق الرأسَ أيُّ عقدة. إن وضع عقدة وهمية قبل الرأس يمنح كل عقدة، بما فيها الرأس، عقدةً سابقة، لذا يكفي سطر واحد لفك الارتباط في جميع الحالات. عندئذٍ تبدأ الإجابة من العقدة التالية للعقدة الوهمية. ويعالج التحقق مما إذا كان المؤشر المتقدم قد تجاوز نهاية القائمة بعد n خطوات الحالة نفسها دون الحاجة إلى العقدة الإضافية.
ما التعقيد الزمني وتعقيد المساحة لإزالة العقدة رقم n من النهاية؟
يستغرق الأمر زمنًا قدره O(L) لقائمة مكوّنة من L عقد، إذ عليك الوصول إلى النهاية لمعرفة مكان الهدف. يستخدم كلٌّ من العد أولًا وطريقة المؤشرين ذاكرة إضافية قدرها O(1). أمّا نسخ القيم إلى مصفوفة فيستخدم O(L).
هل حلّ المؤشرين أسرع من حساب الطول أولًا؟
ليس بفارق كبير: فكلاهما O(L)، وما يزال المؤشران معًا يتحركان عددًا يقارب عدد الحركات في جولتين. الفائدة الحقيقية هي أنك لا تحتاج إلى معرفة الطول مسبقًا، لذا تنجح هذه الطريقة أيضًا عندما تصلك القائمة كتدفّق لا يمكنك قراءته إلا مرة واحدة. وهذه المرورّة الواحدة هي ما يطلبه المحاورون عادةً.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def removeNthFromEnd(values, next, n):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
values = [5, 9, 2, 7, 6] next = [2, 3, 4, -1, 1] n = 2
المتوقع
[5, 2, 6, 7]