Detect Cycle in a linked list (Floyd’s Cycle Detection Algorithm)

Detect Cycle in a linked list: एक linked list दे रखी हैं हमें उस node को return करना है जहाँ से loop or cycle शुरू हो रहा है।

अगर loop exist नहीं करता तो null return करना है।

For example:

तो image में हम देख पा रहें हैं की नोड २ से लिंक्ड लिस्ट से लूप शुरू हो रहा है।

इसलिए हमें output में २ return करना है ।

हम आपको recommend करते हैं की अगर आपने ये question अभी तक try नहीं किया है तो पहले इसे try कर लें।फिर solution देखें।

Floyd’s Cycle Detection Algorithm

Floyd का cycle-detection algorithm एक pointer algorithm है जो केवल दो pointers (slow, fast) का उपयोग करता है, जो विभिन्न गति से आगे बढ़ता है।

उद्देश्य यह निर्धारित करना है कि linked list में कोई loop है या नहीं।

सबसे पहले, आप start के नोड से दो pointer (slow, fast) रखते हैं।

अब हर iteration पर, आप slow पॉइंटर को एक step आगे बढ़ाएं और fast pointer को दो step आगे बढ़ाएं।

आइए इसे हर iteration में one by one flow नीचे pictures में देखते हैं

Consider this is the linked list

1st iteration:

2nd iteration:

3rd iteration:

4th iteration:

5th iteration:

अब हमने ये detect कर लिया की लूप है पर अब हमें ये पता करना है की लूप की स्टार्टिंग किस नोड से हो रही है ।

How to find out starting node of the loop – लूप का स्टार्ट पॉइंट निकालने के लिए हमें क्या करने की आवश्यकता है?

1. अब हमें पता चल गया की लूप exist करता है
2. तो हमें slow pointer को list के starting point यानी head पर ले जाना है और fast pointer को वहीं रखना है।
3. अब हमें दोनों pointer को एक-एक स्टेप ही move करना है
4. अब जिस point पर दोनों pointer मिलेंगे वही हमारा starting of loop or cycle होगा।

तो अब दिमाग में ये सवाल आता है की ऐसा कैसे की जहाँ दोनों pointer मिलेंगे वही हमारा starting node होगा loop का 🤔

इसके लिए हमारे पास एक brief explanation of proof है:

slow pointer से तय की गयी दूरी : x + y 
fast pointer से तय की गयी दूरी : (x + y + z) + y = x + 2y + z
अब चूंकि fast pointer slow pointer की अपेक्षा double speed से 
चलता है और time दोनों के लिए सामान है तो speed distance time के
relation से हम equation बना सकते है :

=> 2(x+y) = x+2y+z
=> x+2y+z = 2x+2y
=> x = z

आइये अब इसका कोड देख लेते है

Detect Cycle in a linked list (Floyd’s Cycle Detection Algorithm) Code:

public class Solution {
     public ListNode detectCycle(ListNode head) {
         ListNode slow = head;
         ListNode fast = head;
         boolean loopDetected = false;
         while (slow != null && fast != null) {
             if (fast.next == null) return null;
             fast = fast.next.next;
             slow = slow.next;
             if (slow == fast) {
                 loopDetected = true;
                 break;
             }
         }
         if (!loopDetected) return null; 
         slow = head;
         while (slow != fast) {
             slow = slow.next;
             fast = fast.next;
         }
         return slow;
     }
 }

---

Next Topic: