Reverse Linked List

Q: كيف تعكس قائمة مترابطة في مكانها؟

مرّر على القائمة باستخدام مؤشرين، يبدأ prev بلا قيمة ويبدأ node عند الرأس. عند كل عقدة، احفظ العقدة التالية لها، ووجّه رابطها إلى prev ، ثم حرّك prev و node خطوة واحدة إلى الأمام. عندما يصل node إلى النهاية، يكون prev هو رأس القائمة المعكوسة.

Q: ما التعقيد الزمني وتعقيد المساحة لعكس قائمة مترابطة؟

يزور الإصدار التكراري كل عقدة مرة واحدة، بزمن O(n) ، ويحتفظ بثلاثة مؤشرات، وبمساحة إضافية O(1) . كما أن نسخ الترتيب إلى مصفوفة أولًا يستغرق زمنًا قدره O(n) ، لكنه يحتاج إلى مساحة إضافية O(n) . يستخدم الإصدار التكراري العودي مساحة O(n) لمكدس الاستدعاءات.

سهلالقائمة المترابطة

+10

لديك قائمة مترابطة أحادية مخزنة في المصفوفة next: تشير العقدة i إلى العقدة next[i]، وتنهي -1 القائمة، ورأس القائمة هو العقدة 0. العقد غير مخزنة بترتيب القائمة، لذا اتبع الروابط.

اعكس القائمة بتغيير اتجاه كل رابط، بحيث تصبح العقدة الأخيرة سابقًا هي الرأس، وتصبح العقدة 0 هي العقدة الأخيرة التي تشير إلى -1. أعد مصفوفة next المحدّثة، التي لها الطول نفسه الذي للإدخال.

الدالة

reverseList(next: integer-array) → integer-array

nextinteger-array: فهرس العقدة التي ترتبط بها كل عقدة، أو ‎-1‎ للعقدة الأخيرة
تُرجعinteger-array: العنصر التالي في المصفوفة المعكوسة

القيود

1 ≤ next.length ≤ 5000
كل قيمة في next[i] إما -1 أو فهرس عقدة من 0 إلى next.length-1.
بدءًا من العقدة 0، تزور القائمة كل عقدة مرة واحدة بالضبط، ثم تصل إلى -1. لا توجد دورة.

أمثلة

المدخلات: next = [1, 2, 3, -1]
المخرجات: [-1, 0, 1, 2]
الشرح: القائمة هي 0 → 1 → 2 → 3. وعند عكسها تصبح 3 → 2 → 1 → 0، لذا ترتبط العقدة 3 بـ 2، والعقدة 2 بـ 1، والعقدة 1 بـ 0، والعقدة 0 بـ -1.

المدخلات: next = [2, -1, 3, 1]
المخرجات: [-1, 3, 0, 2]
الشرح: القائمة هي 0 → 2 → 3 → 1، وعند عكسها تصبح 1 → 3 → 2 → 0. تؤدي كتابة كل رابط جديد عند فهرس العقدة الخاصة به إلى [-1, 3, 0, 2]. أما عكس المصفوفة نفسها فيؤدي إلى [1, 3, -1, 2]، وهذا ليس الشيء نفسه.

المدخلات: next = [-1]
المخرجات: [-1]
الشرح: العقدة الواحدة هي معكوسة نفسها. تظل الرأس والذيل، وتستمر في الارتباط بـ -1.

+11 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك عكس الجزء من القائمة الواقع بين الموضع left والموضع right فقط، وترك العُقد التي تسبقه وتليه في أماكنها؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

عكس القائمة لا ينقل أي عقدة؛ بل يقلب اتجاه كل رابط. تكمن المشكلة في أن رابط العقدة هو الطريقة الوحيدة للوصول إلى بقية القائمة، لذا فإنك تفقد كل ما بعدها بمجرد الكتابة فوقه. يمكنك تجنب المشكلة بتدوين الترتيب أولًا، أو المرور مرة واحدة باستخدام ثلاثة مؤشرات تحفظ الطريق إلى الأمام قبل قلب كل رابط.

دوّن الترتيب، ثم أعد الربط

الفكرة

في هذه المسألة، المؤشر هو فهرس عقدة، والتحرك إلى الأمام يتم باستخدام node = next[node]. تحرّك بدءًا من العقدة 0 حتى تصل إلى -1، وسجّل كل عقدة تمرّ بها. في المثال الثاني، يكون الترتيب الناتج [0, 2, 3, 1].

في القائمة المعكوسة، ترتبط كل عقدة بالعقدة التي سبقتها في ذلك الترتيب: ترتبط 1 بـ 3، و3 بـ 2، و2 بـ 0. لا يوجد ما يسبق أول عقدة في الترتيب، وهي الرأس القديم، لذا ترتبط بـ -1. املأ مصفوفة جديدة بهذه الروابط وأعِدها.

لأن كل رابط يُكتب في مصفوفة جديدة، فلن يُستبدل أي شيء بينما لا تزال بحاجة إليه، ما يجعل من الصعب الوقوع في خطأ في هذه الطريقة. تستغرق هذه الطريقة زمنًا قدره O(n) وتستخدم ذاكرة إضافية قدرها O(n) للترتيب والمصفوفة الجديدة.

الخوارزمية

انتقِل من العقدة 0 إلى -1 وأضِف كل عقدة إلى order.
أنشئ مصفوفة جديدة بالطول نفسه.
عيّن قيمة order[0] إلى -1.
لكل k ≥ 1، عيّن قيمة order[k] إلى order[k-1].
أعِد المصفوفة الجديدة.

def reverseList(next):
    order = []
    node = 0
    while node != -1:
        order.append(node)
        node = next[node]
    reversed_next = [0] * len(next)
    reversed_next[order[0]] = -1  # the old head ends the new list
    for k in range(1, len(order)):
        reversed_next[order[k]] = order[k - 1]
    return reversed_next

اعكس اتجاه الروابط في مرور واحد

الفكرة

يمكنك عكس كل رابط بمجرد وصولك إلى عقدته، إذا تذكرت العقدة التي أتيت منها. احتفظ بـ prev، العقدة التي خلفك، وابدأ بـ -1 لأن الرأس القديم سيصبح العقدة الأخيرة. عند node، يشير الرابط next[node] إلى الأمام؛ فاجعله يشير إلى prev ليشير إلى الخلف.

تُتلف هذه الكتابة طريقتك الوحيدة للمتابعة إلى الأمام، لذا احفظها أولًا في متغير ثالث، after = next[node]. ثم اعكس الرابط، وحرّك كلا المؤشرين خطوة واحدة: prev = node، node = after. في كل لحظة، تشكّل العقد التي خلفك قائمة معكوسة رأسها prev، وتشكل العقد التي أمامك بقية القائمة التي لم تُمس، وتبدأ عند node. عندما تصل node إلى -1، تكون قد عكست كل الروابط ويكون prev هو الرأس الجديد.

في المثال الثاني، تتحرك المؤشرات عبر العقد 0, 2, 3, 1، وتكتب next[0] = -1، وnext[2] = 0، وnext[3] = 2، وnext[1] = 3. تُزار كل عقدة مرة واحدة، بزمن O(n)، والذاكرة الوحيدة المستخدمة هي ثلاثة أعداد صحيحة، O(1).

الخوارزمية

عيّن prev = -1 وnode = 0.
ما دام node لا يساوي -1، فاحفظ after = next[node].
عيّن next[node] = prev.
انتقل إلى التالي: prev = node، ثم node = after.
أعِد next.

def reverseList(next):
    prev = -1  # the node behind the current one; the old head will point to -1
    node = 0
    while node != -1:
        after = next[node]  # save the rest of the list before cutting the link
        next[node] = prev
        prev = node
        node = after
    return next

أخطاء شائعة وحالات حدّية

يتعلق كل خطأ تقريبًا هنا بترتيب الإسنادات الثلاثة، أو بطرفَي القائمة.

استبدال next[node] قبل حفظه. بعد next[node] = prev تختفي الوصلة الأمامية القديمة، وتتجه عملية المرور إلى الخلف بدلًا من الانتقال إلى العقدة التالية.
بدء prev بأي قيمة غير -1. يجب أن تنهي الرأس القديمة القائمة الجديدة. البدء بالقيمة 0 يجعل العقدة 0 تشير إلى نفسها.
عكس المصفوفة بدلًا من عكس الروابط. فالعقد ليست مخزنة بترتيب القائمة، وتُبقي الإجابة كل عقدة في فهرسها الخاص؛ الذي يتغير هو القيم فقط. عكس [2, -1, 3, 1] يعطي [1, 3, -1, 2]، وليس [-1, 3, 0, 2].
التوقف قبل عقدة واحدة باستخدام حلقة شرطها next[node] != -1. يجب أيضًا عكس رابط العقدة الأخيرة، لذا استمر في الحلقة ما دام node != -1.
عكس قائمة طويلة باستخدام الاستدعاء التعاودي. تحتاج قائمة مكوّنة من 5000 عقدة إلى 5000 استدعاء متداخل، وهذا يتجاوز حد Python البالغ 1000.
نسيان الإزاحة في Lua وR، حيث تبدأ المصفوفات من 1. أبقِ فهارس العقد بدءًا من 0 واقرأ next[node + 1]. تحجز Ruby وR الكلمة next، لذا تسمّي الحلول الأولية المَعلمة next_.

أسئلة شائعة4

كيف تعكس قائمة مترابطة في مكانها؟

مرّر على القائمة باستخدام مؤشرين، يبدأ prev بلا قيمة ويبدأ node عند الرأس. عند كل عقدة، احفظ العقدة التالية لها، ووجّه رابطها إلى prev، ثم حرّك prev وnode خطوة واحدة إلى الأمام. عندما يصل node إلى النهاية، يكون prev هو رأس القائمة المعكوسة.

ما التعقيد الزمني وتعقيد المساحة لعكس قائمة مترابطة؟

يزور الإصدار التكراري كل عقدة مرة واحدة، بزمن O(n)، ويحتفظ بثلاثة مؤشرات، وبمساحة إضافية O(1). كما أن نسخ الترتيب إلى مصفوفة أولًا يستغرق زمنًا قدره O(n)، لكنه يحتاج إلى مساحة إضافية O(n). يستخدم الإصدار التكراري العودي مساحة O(n) لمكدس الاستدعاءات.

هل يمكنك عكس قائمة مترابطة بشكل递归؟

نعم. اعكس كل شيء بعد الرأس، ثم اجعل العقدة التالية القديمة للرأس تشير إليه، واجعل رابط الرأس فارغًا. تبدو الطريقة واضحة، لكنها تُجري استدعاءً متداخلًا واحدًا لكل عقدة، لذا قد تؤدي القائمة الطويلة إلى تجاوز سعة مكدس الاستدعاءات. يتوقف Python عند 1000 استدعاء افتراضيًا، وهو حد تتجاوزه قائمة تضم 5000 عقدة.

لماذا يتطلب عكس قائمة مترابطة ثلاثة مؤشرات؟

لعكس رابط عقدة، تحتاج إلى العقدة نفسها والعقدة التي تسبقها، أي مؤشّرين. ويحتفظ المؤشّر الثالث بالعقدة التي تليها، لأن عكس الرابط يمحو المرجع الوحيد إلى بقية القائمة. وبدونه، لا يمكن متابعة المرور.

Python

def reverseList(next):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

next = [1, 2, 3, -1]

المتوقع

[-1, 0, 1, 2]