اكتشاف الحلقات في القوائم المرتبطة باستخدام خوارزمية فلويد

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

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

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

إليك تطبيق Java لخوارزمية فلويد :

boolean hasLoop(Node first) {
    if (first == null) {
        return false; // List does not exist, so no loop
    }

    Node slow, fast; // Create two references.
    slow = fast = first; // Make both refer to the start of the list.

    while (true) {
        slow = slow.next; // One hop.

        if (fast.next != null) {
            fast = fast.next.next; // Two hops.
        } else {
            return false; // No loop.
        }

        if (slow == null || fast == null) {
            return false; // No loop.
        }

        if (slow == fast) {
            return true; // Loop detected.
        }
    }
}

تأخذ هذه الخوارزمية تعقيد مساحة O(1) وتعمل في وقت O(n)، مما يجعلها فعالة في الذاكرة وتستغرق وقتًا معقولًا.