أفضل خوارزمية لاختبار ما إذا كانت القائمة المرتبطة بها دورة

Question

ما هي أفضل خوارزمية (إيقاف) لتحديد ما إذا كانت القائمة المرتبطة بها دورة؟

[عدل] سيكون تحليل التعقيد المقارب لكل من الزمان والمكان أمرًا رائعًا بحيث يمكن مقارنة الإجابات بشكل أفضل.

[عدل] السؤال الأصلي لم يكن يعالج العقد ذات الدرجة الخارجية> 1، ولكن هناك بعض الحديث حول هذا الموضوع.هذا السؤال يتماشى مع "أفضل خوارزمية لاكتشاف الدورات في رسم بياني موجه".

Answer 1

لديك مؤشرين يتكرران خلال القائمة؛اجعل أحدهما يتكرر مرتين بسرعة الآخر، وقارن مواقعهما في كل خطوة.من أعلى رأسي شيء مثل:

node* tortoise(begin), * hare(begin);
while(hare = hare->next)
{
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    hare = hare->next;
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    tortoise = tortoise->next;
}

O(n)، وهو أفضل ما يمكنك الحصول عليه.

Answer 2

الشرط المسبق:تتبع حجم القائمة (قم بتحديث الحجم عند إضافة عقدة أو حذفها).

كشف الحلقة:

1. احتفظ بالعداد عند اجتياز حجم القائمة.

2. إذا تجاوز العداد حجم القائمة، فهناك دورة محتملة.

تعقيد:على)

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

Answer 3

خذ مؤشرين *p و *q ، وابدأ في اجتياز القائمة المرتبطة "LL" باستخدام كلا المؤشرين:

1) سيحذف المؤشر p العقدة السابقة في كل مرة ويشير إلى العقدة التالية.

2) سوف يتحرك المؤشر q في كل مرة في الاتجاه الأمامي فقط.

شروط:

1) يشير المؤشر p إلى قيمة فارغة ويشير q إلى عقدة ما:الحلقة موجودة

2) يشير كلا المؤشرين إلى القيمة الخالية:لا توجد حلقة هناك

Answer 4

ماذا عن استخدام جدول التجزئة لتخزين العقد التي تمت مشاهدتها بالفعل (تنظر إليها بالترتيب من بداية القائمة)؟ومن الناحية العملية، يمكنك تحقيق شيء قريب من O(N).

بخلاف ذلك، فإن استخدام كومة تم فرزها بدلاً من جدول التجزئة سيؤدي إلى تحقيق O(N log(N)).

Answer 5

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

Answer 6

لن تعمل خوارزمية كونراد رودولف إذا كانت الدورة لا تشير إلى البداية.القائمة التالية ستجعلها حلقة لا نهائية:1->2->3->2.

خوارزمية DrPizza هي بالتأكيد الطريق الصحيح.

Answer 7

في هذه الحالة سيكون كود OysterD هو الحل الأسرع (تلوين قمة الرأس)

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

Answer 8

في هذه الحالة سيكون كود OysterD هو الحل الأسرع (تلوين قمة الرأس)

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

نعم.لقد لاحظت أن الصياغة لم تكن مثالية وأعدت صياغتها.ما زلت أعتقد أن التجزئة الذكية قد تؤدي بشكل أسرع – بشعرة واحدة.وأعتقد أن الخوارزمية الخاصة بك يكون الحل الأفضل، بالرغم من ذلك.

فقط للتأكيد على وجهة نظري:يتم استخدام تلوين Vertec للكشف عن الدورات في التبعيات بواسطة جامعي البيانات المهملة الحديثين، لذلك هناك حالة استخدام حقيقية جدًا لها.يستخدمون في الغالب إشارات البت لإجراء التلوين.

Answer 9

سيكون عليك زيارة كل عقدة لتحديد ذلك.يمكن القيام بذلك بشكل متكرر.لمنعك من زيارة العقد التي تمت زيارتها بالفعل، تحتاج إلى علامة تقول "تمت زيارتها بالفعل".وهذا بالطبع لا يعطيك حلقات.لذا بدلاً من علامة صغيرة، استخدم رقمًا.ابدأ عند 1.تحقق من العقد المتصلة ثم ضع علامة عليها كـ 2 وكررها حتى تتم تغطية الشبكة.إذا واجهت عقدة أقل من العقدة الحالية عند التحقق من العقد، فهذا يعني أن لديك دورة.يتم تحديد طول الدورة بالفرق.

Answer 10

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

يتم تنفيذ نموذج التعليمات البرمجية أدناه وفقًا لهذا الحل.المؤشر الأسرع هو pFast، والمؤشر الأبطأ هو pSlow.

bool HasLoop(ListNode* pHead)
{
    if(pHead == NULL)
        return false;


    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == NULL)
        return false;


    ListNode* pFast = pSlow->m_pNext;
    while(pFast != NULL && pSlow != NULL)
    {
        if(pFast == pSlow)
            return true;


        pSlow = pSlow->m_pNext;


        pFast = pFast->m_pNext;
        if(pFast != NULL)
            pFast = pFast->m_pNext;
    }


    return false;
}

هذا الحل متوفر على مدونتي.هناك مشكلة أخرى تمت مناقشتها في المدونة:ما هي عقدة الإدخال عندما تكون هناك دورة/حلقة في القائمة؟

Answer 11

حل "Hack" (يجب أن يعمل في C/C++):

• اجتياز القائمة، وتعيين الجزء الأخير من next المؤشر إلى 1.
• إذا وجدت عنصرًا بمؤشر مُعلَّم - فارجع صحيحًا والعنصر الأول في الدورة.
• قبل العودة، أعد ضبط المؤشرات مرة أخرى، على الرغم من أنني أعتقد أن إلغاء المرجعية سيعمل حتى مع المؤشرات التي تم وضع علامة عليها.

تعقيد الوقت هو 2ن.يبدو أنه لا يستخدم أي متغيرات زمنية.

Answer 12

هذا هو الحل باستخدام جدول التجزئة (مجرد قائمة في الواقع) لحفظ عنوان المؤشر.

def hash_cycle(node):
    hashl=[]
    while(node):
        if node in hashl:
            return True
        else:
            hashl.append(node)
            node=node.next
    return False

Answer 13

بالتأكيد has_cycle(الرأس):العداد = مجموعة ()

while head is not None:
    if head in counter:
        return True
    else:
        counter.add(head)
        head = head.next