Reorder List
لديك قائمة مترابطة أحادية مخزّنة في مصفوفتين لهما الطول نفسه. تحمل العقدة i القيمة values[i] وترتبط بالعقدة next[i]، وتنهي -1 القائمة، والعقدة 0 هي الرأس. لا تُخزَّن العقد بترتيب القائمة، لذا اتبع الروابط.
سمِّ العقد وفق ترتيبها في القائمة L0, L1, ..., Lk. أعد ترتيب القائمة لتصبح L0, Lk, L1, Lk-1, L2, Lk-2, ...: العقدة الأولى، ثم الأخيرة، ثم الثانية، ثم ما قبل الأخيرة، وهكذا. أعد القيم بهذا الترتيب الجديد.
الدالة
- nextinteger-array
- فهرس العقدة التي ترتبط بها كل عقدة، أو -1 للعقدة الأخيرة
- valuesinteger-array
- القيمة التي تحتويها كل عقدة
- تُرجعinteger-array
- القيم بترتيب القائمة المُعاد ترتيبها
القيود
1 ≤ n ≤ 4000، حيث إنnهو طولnextوطولvalues.-1000 ≤ values[i] ≤ 1000- كل
next[i]يساوي-1أو فهرس عقدة من0إلىn-1. - ابتداءً من العقدة
0، تزور القائمة كل عقدة مرة واحدة بالضبط، ثم تصل إلى-1. لا توجد دورة.
أمثلة
- المدخلات
- next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
- المخرجات
- [1, 5, 2, 4, 3]
- الشرح
- باتباع الروابط من العقدة
0، تُقرأ القائمة هكذا:1, 2, 3, 4, 5. الأول، والأخير، والثاني، وما قبل الأخير يعطون1, 5, 2, 4، وتأتي القيمة الوسطى3أخيرًا.
- المدخلات
- next = [2, 3, 1, -1]values = [10, 30, 20, 40]
- المخرجات
- [10, 40, 20, 30]
- الشرح
- تزور القائمة العقد
0, 2, 1, 3وتقرأ10, 20, 30, 40. يعطي الأول والأخير10, 40، ثم يعطي الزوج الداخلي20, 30.
- المدخلات
- next = [-1]values = [7]
- المخرجات
- [7]
- الشرح
- القائمة التي تحتوي على عقدة واحدة ليس فيها ما يمكن نقله، لذا فالإجابة هي
[7].
سؤال إضافي
هل يمكنك إعادة ترتيب الروابط نفسها باستخدام ذاكرة إضافية O(1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اكتب الترتيب المستهدف لـ
1, 2, 3, 4, 5, 6. ما العُقد التي تأتي من النصف الأمامي للقائمة، وبأي ترتيب تظهر عُقد النصف الخلفي؟يظهر النصف الخلفي معكوسًا:
6, 5, 4. إذا كان النصف الخلفي معكوسًا، فستكون الإجابة قائمتين مدمجتين بأخذ عقدة من كل قائمة بالتناوب.اعثر على المنتصف باستخدام مؤشر بطيء يتحرك عقدة واحدة ومؤشر سريع يتحرك عقدتين. اقطع القائمة بعد المنتصف، واعكس الجزء الثاني بتغيير اتجاه روابطه، ثم شبّك الجزأين معًا عقدةً تلو الأخرى.
الحل
يتناوب الترتيب الجديد بين المقدمة والمؤخرة، لكن القائمة المرتبطة أحادية الاتجاه لا تسير إلا إلى الأمام. قسّم المهمة إلى ثلاث عمليات قياسية على القوائم: اعثر على المنتصف باستخدام مؤشري بطيء وسريع، واعكس النصف الخلفي، ثم شبّك النصفين معًا عقدةً واحدة في كل مرة.
حرّك المؤخرة إلى الأمام، عقدة واحدة في كل مرة
الفكرة
المؤشر هنا هو فهرس عقدة، والتحرك إلى الأمام يكون باستخدام node = next[node]. تأتي العقدة الأخيرة بعد العقدة الأولى، لذا افصل العقدة الأخيرة وأدرجها بعد العقدة الحالية، ثم كرر ذلك بعد عقدتين. بالنسبة إلى 1, 2, 3, 4, 5، ينتج عن ذلك 1, 5, 2, 3, 4، ثم 1, 5, 2, 4, 3. توقف عندما يتبقى أقل من عقدتين بعد العقدة الحالية.
يتطلب العثور على العقدة التي تسبق الأخيرة السير حتى النهاية في كل جولة. يتقلص طول المسارات بمقدار عقدتين في كل جولة، ليبلغ إجمالي الحركات نحو n²/4: أربعة ملايين حركة لـ 4000 عقدة.
الخوارزمية
- عيّن
cur = 0. - ما دام هناك عقدتان على الأقل بعد
cur، تحرّك عبرbeforeبدءًا منcurحتى يصبحnext[next[before]] == -1، بحيث تكونtail = next[before]هي العقدة الأخيرة. - افصلها بتعيين
next[before] = -1، ثم أدرجها:next[tail] = next[cur]وnext[cur] = tail. - حرّك
curإلىnext[tail]وكرّر. - تحرّك بدءًا من العقدة
0واجمع القيم.
def reorderList(next, values):
cur = 0
# While at least two nodes follow cur, move the last node right after cur.
while next[cur] != -1 and next[next[cur]] != -1:
before = cur
while next[next[before]] != -1: # find the node before the tail
before = next[before]
tail = next[before]
next[before] = -1
next[tail] = next[cur]
next[cur] = tail
cur = next[tail]
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return resultانسخ القيم واقرأ من كلا الطرفين
الفكرة
يصل المصفوفة إلى عنصرها الأخير في خطوة واحدة. انسخ القيم بترتيب القائمة، [1, 2, 3, 4, 5] في المثال الأول، ثم اقرأ باستخدام lo من الأمام وhi من الخلف: خذ lo، ثم خذ hi، وحرّكهما نحو الداخل ما دام lo < hi. ينتج عن ذلك 1, 5, 2, 4؛ وإذا كان الطول فرديًا، يلتقي المؤشران عند العنصر الأوسط 3، الذي يأتي أخيرًا.
يستغرق ذلك زمنًا قدره O(n) وذاكرة إضافية قدرها O(n)، ولا تتغير الروابط أبدًا.
الخوارزمية
- ابدأ من العقدة
0وأضف كل قيمة إلىinOrder. - عيّن
lo = 0واجعلhiيساوي الفهرس الأخير. - ما دام
lo < hi، أضفinOrder[lo]وinOrder[hi]، ثم حرّكloإلى الأعلى وhiإلى الأسفل. - إذا كان
lo == hi، فأضف القيمة الوسطى.
def reorderList(next, values):
# Write the values out in list order.
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
# Take from the front and the back in turn.
result = []
lo, hi = 0, len(in_order) - 1
while lo < hi:
result.append(in_order[lo])
result.append(in_order[hi])
lo += 1
hi -= 1
if lo == hi: # odd length: the middle value comes last
result.append(in_order[lo])
return resultاعثر على المنتصف، واعكس النصف الخلفي، وشبّك الجزأين بالتناوب
الفكرة
بالنسبة إلى 1, 2, 3, 4, 5, 6، الإجابة هي 1, 6, 2, 5, 3, 4: النصف الأمامي 1, 2, 3 بالترتيب، بالتناوب مع النصف الخلفي 4, 5, 6 مقروءًا بالعكس. لذا اقطع القائمة من المنتصف، واعكس النصف الخلفي، ثم شابك بينهما.
يتحرك slow رابطًا واحدًا، بينما يتحرك fast رابطين، لذا يتوقف slow عند العقدة الأخيرة من النصف الأمامي: العقدة 3، سواء أكان عدد العقد خمسًا أم ستًا. يؤدي القطع بعد هذه العقدة إلى جعل النصف الأمامي أطول بعقدة واحدة عندما يكون الطول فرديًا، وتكون تلك العقدة نهاية الإجابة. يأخذ التشابك عقدة من كل نصف بالتناوب حتى ينفد النصف الخلفي.
تُلمَس كل عقدة عددًا ثابتًا من المرات، مع استخدام بضعة فهارس من الذاكرة. ينسخ R متجه الروابط عند أول تغيير فيه، لذا تكون الذاكرة في R هي O(n).
الخوارزمية
- حرّك
slowرابطًا واحدًا وfastرابطين ما دامnext[fast]وnext[next[fast]]لا يساويان-1. - عيّن
second = next[slow]، ثمnext[slow] = -1. - اعكس القائمة التي تبدأ عند
second؛ وسيكون رأسها الجديدprev. - تشابك: ما دام
secondلا يساوي-1، اربطfirstبـsecondوsecondبالقيمة القديمة لـnext[first]، ثم حرّك كليهما إلى الأمام. - سر من العقدة
0واجمع القيم.
def reorderList(next, values):
# 1. Find the middle: slow stops on the last node of the first half.
slow = fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
# 2. Reverse the second half.
prev = -1
while second != -1:
after = next[second]
next[second] = prev
prev = second
second = after
# 3. Weave: one node from the front half, one from the reversed back half.
first, second = 0, prev
while second != -1:
first_after, second_after = next[first], next[second]
next[first] = second
next[second] = first_after
first, second = first_after, second_after
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return result
أخطاء شائعة وحالات حدّية
- عدم قطع القائمة بعد المنتصف. من دون
next[slow] = -1، يظل النصف الأمامي يشير إلى النصف الخلفي، وبعد التداخل تلتف القائمة على نفسها. - الكتابة فوق رابط قبل حفظه. أثناء العكس والتداخل، اقرأ
next[node]في متغير أولًا، وإلا فسيضيع باقي القائمة. - مواصلة التداخل حتى نهاية النصف الأمامي. عندما يكون الطول فرديًا، تتكرر الحلقة مرة أخرى وتكون قيمة
secondهي-1، ثم تقرأnext[-1]. - اعتبار ترتيب المصفوفة هو ترتيب القائمة. في المثال الأول، تكون
valuesهي[1, 3, 5, 2, 4]، لكن ترتيب القائمة هو1, 2, 3, 4, 5. - في Lua وR، تبدأ المصفوفات من 1. أبقِ فهارس العقد تبدأ من 0، واقرأ
next[node + 1].
أسئلة شائعة3
لماذا نعكس النصف الثاني من القائمة؟
تقرأ الإجابة النصف الخلفي من عقدته الأخيرة إلى الأولى، بينما لا تتحرك القائمة المرتبطة أحادية الاتجاه إلا إلى الأمام. يتيح عكس النصف الخلفي مرة واحدة، بزمن O(n)، للدمج المرور عبر كلا النصفين إلى الأمام.
ما هو التعقيد الزمني لإعادة ترتيب القائمة؟
تعمل الطريقة داخل القائمة في زمن O(n) مع ذاكرة إضافية O(1): إذ تزور كل من إيجاد الوسط وعكس القائمة ودمجها كل عقدة عددًا ثابتًا من المرات. كما أن نسخ القيم إلى مصفوفة يستغرق زمنًا O(n)، لكنه يحتاج إلى ذاكرة O(n)، بينما يستغرق تحريك الذيل إلى الأمام عقدةً واحدة في كل مرة زمنًا O(n²).
أين يقع المنتصف عندما تحتوي القائمة على عدد زوجي من العقد؟
أوقف المؤشر البطيء عند العقدة الأخيرة من النصف الأمامي. عند وجود ست عقد، يكون النصفان ثلاثة وثلاثة؛ وعند وجود خمس عقد، يكونان ثلاثة واثنتين. عندها تكون العقدة الإضافية هي نهاية الإجابة، وهي الموضع الذي يضع فيه الترتيب القيمة الوسطى.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def reorderList(next, values):
# اكتب الشيفرة هنااختبار #1
اختبار #2
اختبار #3
الوسائط
next = [3, 4, -1, 1, 2] values = [1, 3, 5, 2, 4]
الإخراج المتوقع
[1, 5, 2, 4, 3]