Linked List Cycle

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

يستغرق كلا الأسلوبين زمنًا قدره O(n) ، لأن كل عقدة تُمرَّر عددًا محدودًا من المرات. يتطلب تحديد العقد التي تمت زيارتها ذاكرة إضافية قدرها O(n) . تحتاج مؤشرات فلويد السريعة والبطيئة إلى O(1) : رقمي عقدتين.

Q: لماذا لا يستطيع المؤشر السريع تخطّي المؤشر البطيء؟

داخل الدورة، في كل جولة يتحرك fast عقدتين و slow عقدة واحدة، لذا تقل المسافة التي لا يزال يتعين على fast قطعها للوصول إلى slow بمقدار واحد بالضبط. والمسافة التي تنقص بمقدار واحد في كل جولة تسير على النحو 3، 2، 1، 0، ولا يمكنها تجاوز الصفر، لذا يلتقي المؤشران عند عقدة.

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

+10

تُخزَّن القائمة المرتبطة في المصفوفة next: تشير العقدة i إلى العقدة next[i]، وتعني -1 أن القائمة تنتهي عندها. الرأس هو العقدة 0. اتبع الروابط بدءًا من الرأس وأعِد true إذا عدت في أي وقت إلى عقدة سبق أن زرتها، أو false إذا وصلت إلى النهاية. لا تُحتسب العقد التي لا تصل إليها أثناء التنقل، حتى لو كانت تشير بعضها إلى بعض في حلقة.

الدالة

hasCycle(next: integer-array) → boolean

nextinteger-array: الرابط الخاص بكل عقدة: next[i] هي العقدة التي تلي العقدة i، أو -1
تُرجعboolean: true إذا أعادت الجولة بدءًا من العقدة 0 زيارة عقدة، وfalse إذا وصلت إلى -1

القيود

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
قد ترتبط عدة عقد بالعقدة نفسها، وقد يتعذر الوصول إلى بعض العقد من الرأس.

أمثلة

المدخلات: next = [1, 2, 3, 1]
المخرجات: true
الشرح: يمرّ المسار بالعُقد 0 و1 و2 و3، ثم يعود إلى 1. تتم زيارة العقدة 1 مرتين، لذا تحتوي القائمة على دورة تمرّ بالعُقد 1 و2 و3.

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

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

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

سؤال إضافي

هل يمكنك أيضًا العثور على العقدة التي تبدأ عندها الدورة، مع استخدام ذاكرة إضافية O(1)؟

تلميحات

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

فُتح 0 من 3

الحل

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

علِّم العقد التي تزورها

الفكرة

ابدأ من العقدة 0 وضع علامة على كل عقدة عند مغادرتها. إذا وصلت إلى عقدة عليها علامة بالفعل، فهذا يعني أن المسار عاد إليها، ومن تلك النقطة سيستمر في التكرار إلى الأبد: وهذه دورة. في المثال 1، تضع علامات على 0 و1 و2 و3، ويؤدي الرابط من العقدة 3 إلى العقدة 1 التي عليها علامة.

ترقيم العقد يبدأ من 0 إلى n-1، لذا فإن مصفوفة منطقية بطول n تصلح كمجموعة للعقد التي تمت زيارتها. في قائمة مترابطة مبنية من كائنات، ستضع مراجع العقد في مجموعة تجزئة بدلًا من ذلك؛ الفكرة هي نفسها.

توضع علامة على كل عقدة مرة واحدة على الأكثر، ويتوقف المسار عند أول تكرار أو عند -1، لذا يستغرق الأمر n خطوات على الأكثر: زمن O(n) وذاكرة O(n) للعلامات.

الخوارزمية

أنشئ مصفوفة من القيم المنطقية visited بطول n، وجميع عناصرها false.
عيّن node = 0.
ما دام node لا يساوي -1، فأعِد true إذا كانت visited[node] تساوي true بالفعل.
وإلا، عيّن visited[node] وانتقل إلى next[node].
عندما يصل المسار إلى -1، أعِد false.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

المؤشران السريع والبطيء (اكتشاف الدورة لخوارزمية فلويد)

الفكرة

ابدأ بمؤشرين عند الرأس. يتبع slow رابطًا واحدًا في كل دورة، ويتبع fast رابطين. إذا انتهت القائمة، يصل fast إلى -1 أولًا، وتُعيد false. إذا كانت هناك دورة، يدخلها fast أولًا ويواصل الدوران حتى يصل إليها slow أيضًا.

بمجرد أن يصبح كلاهما داخل الدورة، يكتسب fast في كل دورة عقدة واحدة بالضبط على slow. تقل المسافة التي لا يزال على fast قطعها للوصول إلى slow بمقدار واحد في كل دورة، لذا تصبح صفرًا ويستقر المؤشران على العقدة نفسها. وبما أن fast يكتسب عقدة واحدة في كل مرة، فلا يمكنه أبدًا تجاوز slow.

في المثال 1، بعد دورة واحدة يكون slow عند العقدة 1 وfast عند العقدة 2. بعد دورتين يكون slow عند العقدة 2، ويكون fast قد مرّ بالعقدتين 3 و1. بعد ثلاث دورات يكون كلاهما عند العقدة 3، لذا تكون الإجابة true.

يحتاج slow إلى n دورات كحد أقصى للدخول إلى الدورة، وبمجرد دخوله إليها يلتقيان قبل أن يكمل دورة كاملة، لذا فإن الزمن هو O(n). الذاكرة الوحيدة المستخدمة هي رقما العقدتين.

الخوارزمية

عيّن slow = 0 وfast = 0.
طالما أن fast لا يساوي -1 وأن next[fast] لا يساوي -1، حرّك slow رابطًا واحدًا وfast رابطين.
بعد كل حركة، أرجِع true إذا كانا على العقدة نفسها.
عندما تتوقف الحلقة، يكون fast قد وصل إلى النهاية: أرجِع false.

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

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

تتعلق الأخطاء هنا بنهاية القائمة وبالعُقد التي تُحتسب.

تحريك fast خطوتين من دون التحقق من كلتيهما. يجب أن تكون كل من fast وnext[fast] عقدة حقيقية قبل قراءة next[next[fast]]؛ وإلا فستقرأ next[-1]، ما يؤدي إلى تعطل البرنامج في معظم اللغات، بينما يُرجع بهدوء العنصر الأخير في Python.
مقارنة المؤشرات قبل تحريكها. يبدأ كلاهما عند العقدة 0، لذا فإن التحقق في بداية الحلقة سيُبلّغ عن وجود دورة في كل قائمة.
النظر إلى المصفوفة بأكملها بدلًا من المسار المتَّبع. في [-1, 2, 1] تشكّل العقدتان 1 و2 حلقة، لكن المسار من الرأس ينتهي فورًا، لذا تكون الإجابة false. ومن الخطأ أيضًا التحقق مما إذا كانت قيمة ما تتكرر في next: ففي [4, 4, 4, 4, -1] ترتبط عدة عقد بالعقدة 4، ولا توجد دورة.
افتراض أن الدورة يجب أن تعود إلى الرأس. في [1, 2, 3, 4, 4] ترتبط العقدة الأخيرة بنفسها، وفي [0] ترتبط عقدة الرأس بنفسها.

أسئلة شائعة4

كيف تعمل خوارزمية فلويد لاكتشاف الدورات؟

يبدأ مؤشّران عند الرأس: يتحرّك أحدهما بمقدار وصلة واحدة في كل خطوة، والآخر بمقدار وصلتين. إذا لم توجد دورة، يصل المؤشّر السريع إلى النهاية. أمّا إذا وُجدت دورة، فينتهي بهما المطاف داخلها، ويقلّص المؤشّر السريع الفجوة بمقدار عقدة واحدة في كل خطوة، حتى يلتقيا عند العقدة نفسها.

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

يستغرق كلا الأسلوبين زمنًا قدره O(n)، لأن كل عقدة تُمرَّر عددًا محدودًا من المرات. يتطلب تحديد العقد التي تمت زيارتها ذاكرة إضافية قدرها O(n). تحتاج مؤشرات فلويد السريعة والبطيئة إلى O(1): رقمي عقدتين.

لماذا لا يستطيع المؤشر السريع تخطّي المؤشر البطيء؟

داخل الدورة، في كل جولة يتحرك fast عقدتين وslow عقدة واحدة، لذا تقل المسافة التي لا يزال يتعين على fast قطعها للوصول إلى slow بمقدار واحد بالضبط. والمسافة التي تنقص بمقدار واحد في كل جولة تسير على النحو 3، 2، 1، 0، ولا يمكنها تجاوز الصفر، لذا يلتقي المؤشران عند عقدة.

هل يمكنك اكتشاف الدورة عن طريق عدّ الخطوات؟

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

Python

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

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

الحالة 1

الحالة 2

الحالة 3

المدخلات

next = [1, 2, 3, 1]

المتوقع

true