Floyd's tortoise and hare ஐ பயன்படுத்தி சைக்கிலை எப்படி கண்டறிவது?

Question

Accepted Answer

**Floyd's சைக்கிள் கண்டறிதல்** ஒரு வரிசையில் (linked list போன்ற) இரண்டு pointer களை வெவ்வேறு வேகத்தில் நகர்த்தி ஒரு loop ஐ கண்டறிகிறது. சைக்கிள் இருந்தால், வேகமான pointer மெதுவான pointer ஐ பிடித்து சந்திக்கிறது. இது **O(1)** கூடுதல் இடத்தை பயன்படுத்துகிறது.

## கருத்து

**slow** pointer ஐ ஒரு step அளவிலும், **fast** pointer ஐ இரண்டு step அளவிலும் நகர்த்தவும். சைக்கிளில், இடைவெளி ஒவ்வொரு step இல் ஒன்றாக குறைந்து, எனவே அவை மோதல் செய்ய வேண்டும்; சைக்கிள் இல்லாமல், 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).

hash-set முறை மேலும் வேலை செய்கிறது ஆனால் O(n) இடத்தை செலவிடுகிறது; Floyd's மாறிலி இடத்தைப் பயன்படுத்துகிறது.

## பயன்படுத்தும் போது / குறைபாடுகள்

**linked-list loop கண்டறிதல்**, சைக்கிள் ஆரம்பம் கண்டறிதல், மற்றும் functional graphs (ஒவ்வொரு node க்கும் ஒரு successor உள்ளது) க்கு சைக்கிள் கண்டறிதலுக்கு பயன்படுத்தவும். எப்போதும் `fast.next` ஐ பாதுகாக்க null dereferences தவிர்க்கவும். பொதுவான graphs க்கு, பதிலாக recursion stack உடன் DFS பயன்படுத்தவும்.

## ஏன் முக்கியம்

சைக்கிள் கண்டறிதல் பாதுகாப்பான traversal க்கு அவசியம் — கண்டறியப்படாத loop என்றால் infinite iteration.

Floyd's algorithm ஒரு O(n)-space சிக்கலை O(1) space இல் ஒரு clever invariant உடன் தீர்ப்பதற்கான அழகான உதாரணம்.

இது linked-list interviews இல் மற்றும் state machines மற்றும் number sequences இல் infinite loops கண்டறிதலில் தோன்றும்.