Floyd च्या कासव आणि सरकण्याराने सायकल कसे शोधता येते?

Question

IT Interview Practice · Accepted Answer

**Floyd's cycle detection** अनुक्रमांमध्ये (जसे लिंक केलेली यादी) दोन निर्देशक वापरून लूप शोधते जो भिन्न गतीने चालते. जर सायकल अस्तित्वात असेल, तर वेगवान निर्देशक हळुवार निर्देशकाला पकडते. **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) जागा खर्च करते; Floyd's स्थिर जागा वापरते.

## कधी वापरायचे / अडचणी

**लिंक-यादी लूप शोधणी**, सायकलचा प्रारंभ शोधण्यासाठी, आणि कार्यात्मक आलेखांमध्ये सायकल शोधणीसाठी वापरा (प्रत्येक नोड एक उत्तराधिकारी आहे). `fast.next` ला रक्षण करा ताकि शून्य डिरेफरेन्सिंगचे कारण न होऊ शकेल. सामान्य आलेखांसाठी, रिकर्शन स्टॅकसह DFS वापरा.

## हे महत्वाचे का आहे

सायकल शोधणे सुरक्षित ट्रॅव्हर्सलसाठी आवश्यक आहे — एक अशोधित लूप म्हणजे अनंत पुनरावृत्ती.

Floyd चा अल्गोरिदम हा O(n)-स्पेस समस्या O(1) स्पेसमध्ये क्लेवर इनव्हेरिएंटसह सोडविण्याचे एक सुंदर उदाहरण आहे.

ते लिंक-यादी मुलाखतींमध्ये आणि अनंत लूप शोधणीमध्ये स्टेट मशीन आणि संख्या अनुक्रमांमध्ये दिसले.

कल्पना

उदाहरण

जटिलता

कधी वापरायचे / अडचणी

हे महत्वाचे का आहे

संबंधित प्रश्न