Floyd's cycle detection ले दुई pointers प्रयोग गरेर विभिन्न गतिमा चलाएर sequence (जस्तै linked list) मा loop खोज्छ। यदि cycle अवस्थित छ भने, fast pointer ले अन्ततः slow pointer लाई पकड़ेर मिलिन्छ। यसले O(1) अतिरिक्त स्पेस प्रयोग गर्छ।
slow pointer लाई एक कदम र fast pointer लाई दुई कदम अगाडि सारनुहोस्। cycle मा, अन्तर प्रत्येक कदमले एक कम हुन्छ, त्यसैले तिनीहरू अवश्य टुट्नुपर्छ; cycle बिना, fast अन्तमा पुग्छ।
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
Hash-set दृष्टिकोण पनि काम गर्छ तर O(n) स्पेस खर्च गर्छ; Floyd को स्थिर स्पेस प्रयोग गर्छ।
linked-list loop detection, cycle को सुरुवात खोज्न, र functional graphs (प्रत्येक node को एक successor छ) मा cycles पत्ता लगाउन प्रयोग गर्नुहोस्। null dereferences बचाउन fast.next लाई सधैं गार्ड गर्नुहोस्। सामान्य graphs को लागि, recursion stack को साथ DFS प्रयोग गर्नुहोस्।
Cycle detection सुरक्षित traversal को लागि आवश्यक छ — पत्ता नलागेको loop मतलब अनन्त पुनरावृत्ति।
Floyd को algorithm एक सुन्दर उदाहरण हो जसले O(n)-space समस्यालाई clever invariant को साथ O(1) space मा समाधान गर्छ।
यो linked-list interviews मा र state machines र number sequences मा अनन्त loops detect गर्दा देखा पर्छ।