Floyd's tortoise and hare کے ساتھ آپ cycle کو کیسے detect کرتے ہیں؟

Question

Accepted Answer

**Floyd's cycle detection** ایک sequence (جیسے linked list) میں loop تلاش کرتا ہے دو pointers استعمال کرتے ہوئے جو مختلف رفتار سے حرکت کرتے ہیں۔ اگر cycle موجود ہے تو fast pointer آخری کار slow pointer کو پکڑتا ہے اور ملتا ہے۔ یہ **O(1)** اضافی space استعمال کرتا ہے۔

## یہ خیال

**slow** pointer کو ایک قدم آگے بڑھائیں اور **fast** pointer کو دو قدم آگے بڑھائیں۔ cycle میں، فاصلہ ہر قدم سے ایک کم ہو جاتا ہے، تو وہ ضرور ٹکرائیں گے؛ cycle کے بغیر، 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
```

## Complexity

- **Time:** O(n). **Space:** O(1).

ایک hash-set approach بھی کام کرتا ہے لیکن O(n) space خرچ کرتا ہے؛ Floyd's مسلسل space استعمال کرتا ہے۔

## کب استعمال کریں / خطرات

**linked-list loop detection**، cycle کی شروعات تلاش کرنے، اور functional graphs میں cycles detect کرنے کے لیے استعمال کریں (ہر node کا ایک successor ہے)۔ ہمیشہ `fast.next` کو null dereferences سے بچانے کے لیے محفوظ رکھیں۔ عام graphs کے لیے، بجائے اس کے recursion stack کے ساتھ DFS استعمال کریں۔

## یہ کیوں اہم ہے

Cycles کی شناخت محفوظ traversal کے لیے ضروری ہے — ایک غیر محسوس شدہ loop کا مطلب لامحدود iteration ہے۔

Floyd's algorithm ایک خوبصورت مثال ہے جو O(n)-space مسئلے کو O(1) space میں ایک ہوشیار invariant کے ساتھ حل کرتے ہوئے۔

یہ linked-list interviews میں اور state machines اور number sequences میں لامحدود loops کی شناخت میں ظاہر ہوتا ہے۔