كيف تكتشف دورة باستخدام خوارزمية السلحفاة والأرنب (Floyd's Tortoise and Hare)؟

Question

Accepted Answer

**كشف الدورات في خوارزمية فلويد** يجد حلقة في تسلسل (مثل القائمة المرتبطة) باستخدام مؤشرين يتحركان بسرعات مختلفة. إذا كانت دورة موجودة، فإن المؤشر السريع في النهاية يلحق ويلتقي بالمؤشر البطيء. ويستخدم مساحة إضافية **O(1)**.

## الفكرة

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

## مثال

```python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # +1 step
        fast = fast.next.next       # +2 steps
        if slow is fast:            # pointers met -> cycle
            return True
    return False                    # fast hit the end -> no cycle
```

## التعقيد

- **الوقت:** O(n). **المساحة:** O(1).

طريقة مجموعة التجزئة تعمل أيضاً لكنها تكلف O(n) مساحة؛ خوارزمية فلويد تستخدم مساحة ثابتة.

## متى تستخدم / المزالق

استخدم لـ **كشف الحلقات في القوائم المرتبطة**، وإيجاد بداية الدورة، والكشف عن الدورات في الرسوم البيانية الوظيفية (كل عقدة لها خليفة واحد). احمِ دائماً `fast.next` لتجنب إلغاء الإشارات الفارغة. للرسوم البيانية العامة، استخدم DFS مع stack التكرار بدلاً من ذلك.

## لماذا يهم

الكشف عن الدورات ضروري للعبور الآمن — حلقة غير مكتشفة تعني التكرار اللانهائي.

خوارزمية فلويد هي مثال جميل على حل مشكلة بمساحة O(n) في مساحة O(1) بمتغير ذكي.

تظهر في مقابلات القائمة المرتبطة والكشف عن الحلقات اللانهائية في آلات الحالة وتسلسلات الأرقام.