Palindrome Linked List

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

كل طريقة تعقيدها O(L) لقائمة تتكون من L عُقد، لأن كل قيمة يجب مقارنتها. يتطلب نسخ القيم إلى مصفوفة أو إلى مكدس ذاكرة إضافية بحجم O(L) ؛ أما عكس النصف الثاني في مكانه فيتطلب O(1) .

Q: كيف يعثر المؤشر السريع والمؤشر البطيء على منتصف القائمة المرتبطة؟

كلاهما يبدأان من الرأس، ويقطع المؤشر السريع خطوتين مقابل كل خطوة يقطعها المؤشر البطيء. عندما يصل المؤشر السريع إلى النهاية، يكون قد اجتاز القائمة كلها، بينما يكون المؤشر البطيء قد اجتاز نصفها.

Q: هل يؤدي عكس نصف القائمة إلى إتلاف المُدخل؟

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

سهلالقائمة المترابطة المؤشران السريع والبطيء مؤشران

+10

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

أعِد true إذا كانت القيم المقروءة من الرأس إلى النهاية هي نفسها عند قراءتها من النهاية إلى الرأس، وfalse خلاف ذلك.

الدالة

isPalindrome(next: integer-array, values: integer-array) → boolean

nextinteger-array: فهرس العقدة التي ترتبط بها كل عقدة، أو ‎-1‎ للعقدة الأخيرة
valuesinteger-array: القيمة التي تحتفظ بها كل عقدة
تُرجعboolean: صحيح إذا كانت القائمة تُقرأ بالطريقة نفسها في كلا الاتجاهين

القيود

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

أمثلة

المدخلات: next = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
المخرجات: true
الشرح: تزور الروابط العقد 0, 4, 1, 3, 2، لذا تكون القائمة 3, 1, 4, 1, 3. يتطابق العددان 3، ويتطابق العددان 1، أما 4 في المنتصف فلا نظير له للتحقق منه.

المدخلات: next = [2, -1, 3, 1]values = [4, 4, 9, 9]
المخرجات: true
الشرح: تزور القائمة العقد 0, 2, 3, 1 وتقرأ 4, 9, 9, 4، وهو الأمر نفسه في كلا الاتجاهين.

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

سؤال إضافي

هل يمكنك تنفيذ ذلك في زمن O(L) وباستخدام ذاكرة إضافية O(1)؟

تلميحات

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

فُتح 0 من 3

الحل

يتحقق اختبار التناظر من كل قيمة بمقارنتها بنظيرتها من الطرف الآخر. لا تسير القائمة المرتبطة أحادية الاتجاه إلا إلى الأمام، لذا تكمن الصعوبة في قراءة النصف الخلفي بترتيب عكسي. تنسخ المصفوفة القيم وتحقق ذلك باستخدام ذاكرة O(L)، حيث يشير L إلى عدد العُقد؛ أما عكس الروابط في النصف الثاني فيحقق ذلك باستخدام O(1).

انسخ القيم إلى مصفوفة

الفكرة

المؤشر هنا هو فهرس عقدة، والانتقال إلى الأمام يكون عبر node = next[node]. مرّ على القائمة مرة واحدة وانسخ كل قيمة إلى مصفوفة، يمكنك القراءة منها من الطرفين. قارن القيمة الأولى بالأخيرة، وحرّك كلا الفهرسين نحو الوسط، وأعِد false عند أي اختلاف. إذا كان الطول فرديًا، تكون القيمة الوسطى شريكة نفسها.

لا بد من قراءة كل قيمة، لذا فإن الزمن O(L) هو الأفضل الممكن. والتكلفة هي L أعداد صحيحة إضافية.

الخوارزمية

انتقل من العقدة 0 إلى -1 وأضف كل values[node] إلى مصفوفة.
عيّن i = 0 وعيّن j إلى الفهرس الأخير.
ما دام i < j، فأعِد false إذا اختلفت القيمتان، وإلا فزِد i وأنقِص j.
أعِد true.

def isPalindrome(next, values):
    # Write the values out in list order.
    seq = []
    node = 0
    while node != -1:
        seq.append(values[node])
        node = next[node]
    # Compare from both ends toward the middle.
    i = 0
    j = len(seq) - 1
    while i < j:
        if seq[i] != seq[j]:
            return False
        i += 1
        j -= 1
    return True

اعكس النصف الثاني في موضعه

الفكرة

اعكس الروابط في النصف الخلفي بدلًا من نسخه: فالسير بدءًا من العقدة الأخيرة القديمة يقود حينها نحو الوسط. للعثور على الوسط، حرّك fast رابطتين مقابل كل رابطة يحرّكها slow، ما دام أمام fast رابطتان. يتوقف slow عند العقدة الأخيرة من النصف الأول، وهي العقدة الوسطى عندما يكون L فرديًا. في المثال الأول، ينتقل slow عبر 0 → 4 → 1 بينما ينتقل fast عبر 0 → 1 → 2، لذا يتوقف slow عند 4.

اعكس العقد التي تأتي بعد slow، ثم سر بـleft بدءًا من الرأس وبـright بدءًا من النصف المعكوس معًا: 3 مع 3، ثم 1 مع 1. لا يكون النصف المعكوس أطول من النصف الأول أبدًا، لذا فإن التوقف عند انتهاء right يقارن الأزواج المهمة بالضبط. تمر كل مرحلة على L عقدة كحد أقصى، وتخزّن بضعة أعداد صحيحة. في R، يؤدي تغيير next_ إلى نسخ المتجه مرة واحدة، لذا تستخدم R ذاكرة O(L).

الخوارزمية

عيّن slow = fast = 0. ما دام كلٌّ من next[fast] وnext[next[fast]] لا يساوي -1، حرّك slow رابطًا واحدًا وfast رابطين.
اعكس القائمة التي تبدأ عند next[slow]: لكل عقدة، احفظ رابطها، ووجّهه إلى prev، ثم حرّك prev والعقدة إلى الأمام.
عيّن left = 0 وright = prev، وهو رأس النصف المعكوس.
ما دام right != -1، أعد false عند وجود اختلاف، وإلا فحرّك المؤشرين رابطًا واحدًا.
أعد true.

def isPalindrome(next, values):
    # Find the middle: fast moves two links for every one link slow moves.
    slow = 0
    fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    # slow is the last node of the first half (the middle node when the length is odd).
    # Reverse the links of the second half.
    prev = -1
    node = next[slow]
    while node != -1:
        after = next[node]
        next[node] = prev
        prev = node
        node = after
    # prev is the old last node, now the head of the reversed half.
    left = 0
    right = prev
    while right != -1:
        if values[left] != values[right]:
            return False
        left = next[left]
        right = next[right]
    return True

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

التحقق من المصفوفات بدلًا من القائمة. في المثال الثالث، تكون values هي [1, 2, 1]، لكن القائمة تقرأ 1, 1, 2.
اختبار next[fast] != -1 فقط. عندها قد ينتقل fast إلى -1 ويقرأ next[-1]، وهو خارج النطاق في معظم اللغات، ويشير بصمت إلى العنصر الأخير في Python وRuby.
المقارنة حتى تنتهي left بدلًا من right. تظل العقدة الوسطى مرتبطة بالنصف الثاني القديم، لذا يكون المسار انطلاقًا من الرأس هو الأطول.
الكتابة فوق next[node] أثناء عكس الترتيب قبل حفظه، ما يؤدي إلى فقدان بقية القائمة.
في Lua وR، حيث تبدأ المصفوفات من 1، قراءة next[node] لمعرّف عقدة يبدأ من 0. اقرأ next[node + 1].

أسئلة شائعة3

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

كل طريقة تعقيدها O(L) لقائمة تتكون من L عُقد، لأن كل قيمة يجب مقارنتها. يتطلب نسخ القيم إلى مصفوفة أو إلى مكدس ذاكرة إضافية بحجم O(L)؛ أما عكس النصف الثاني في مكانه فيتطلب O(1).

كيف يعثر المؤشر السريع والمؤشر البطيء على منتصف القائمة المرتبطة؟

كلاهما يبدأان من الرأس، ويقطع المؤشر السريع خطوتين مقابل كل خطوة يقطعها المؤشر البطيء. عندما يصل المؤشر السريع إلى النهاية، يكون قد اجتاز القائمة كلها، بينما يكون المؤشر البطيء قد اجتاز نصفها.

هل يؤدي عكس نصف القائمة إلى إتلاف المُدخل؟

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

def isPalindrome(next, values):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

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

الإخراج المتوقع

true