लूप डिटेक्शन: लिंक्ड लिस्ट में चक्र की शुरुआत खोजें (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या २.८: वृत्तीय लिंक्ड लिस्ट दी हो तो वह नोड लौटाओ जहाँ लूप शुरू होता है। फ्लॉयड कछुआ-खरगोश, फिर हेड पर रीसेट वाला ट्रिक, साफ जावा में।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

आप एक रास्ते पर दौड़ते हैं जो पहले सीधा है, फिर पार्क के गोल ट्रैक में जुड़ जाता है। जोड़ तब तक नहीं सूझता जब तक वही पेड़ दोबारा न दिखे। एक दोस्त आपके साथ निकलता है और दोगुनी रफ्तार से दौड़ता है। आप दोनों उस घेरे पर कहीं मिलेंगे। मज़े की बात: मिलने के बाद अगर दोस्त वापस रास्ते की शुरुआत पर चला जाए और दोनों एक जैसी चाल से चलें, तो फिर ठीक लूप के द्वार पर मिलते हैं। लिंक्ड लिस्ट पर यही लूप डिटेक्शन है।

यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली चक्र-समस्याओं का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय २ यहीं खत्म होता है।

---

१. रोज़मर्रा की उपमा

एक रनिंग ट्रैक सोचो जिसके साथ पहुँच-सड़क हो:

• पहुँच-सड़क लिस्ट का बिना-लूप वाला हिस्सा है (head से लेकर उस पहले नोड तक जो चक्र पर भी है)।
• अंडाकार ट्रैक ही चक्र है। कोई नोड null पर खत्म होने की बजाय किसी पुराने नोड की ओर next घुमा देता है।
• कछुआ हर बार एक कदम चलता है। खरगोश दो कदम।

अगर अंडाकार नहीं है, खरगोश रास्ते के अंत (null) पर गिर जाता है और काम खत्म: कोई लूप नहीं।

अगर अंडाकार है, खरगोश ट्रैक पर कछुए से जा मिलता है। वे चक्र के अंदर किसी नोड पर टकराते हैं, जरूरी नहीं कि शुरुआत हो। दूसरा चरण शुरुआत ढूँढता है: एक धावक रास्ते की शुरुआत पर लौटता है, दूसरा मिलन-बिंदु पर रहता है, दोनों एक-एक कदम चलते हैं। अगली टक्कर लूप की शुरुआत है।

---

२. समस्या सादे शब्दों में

इनपुट: एक सिंगली लिंक्ड लिस्ट का हेड। लिस्ट सीधी हो सकती है, या उसमें चक्र हो सकता है (किसी नोड का next किसी पहले वाले नोड की ओर)।

आउटपुट: लूप की शुरुआत वाला नोड, या अगर लूप नहीं तो null।

"लूप की शुरुआत" वह पहला नोड है जिसे next फॉलो करते हुए बार-बार पहुँचा जा सके। चित्र में वही नोड है जिसके दो आने वाले किनारे हैं: एक बिना-लूप वाले हिस्से से (या खुद से, अगर पूरा चक्र हेड से शुरू हो), और एक चक्र के पिछले नोड से।

नोड का आकार:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

उदाहरण (अक्षर नोड की पहचान हैं, सिर्फ मान नहीं):

लिस्ट का आकार	लूप कहाँ शुरू	क्यों
A → B → C → D → E → C (E वापस C पर)	C	चक्र का पहला नोड
A → B → C → null	कोई नहीं (null)	सीधी लिस्ट
A → A (स्व-लूप)	A	एक नोड का चक्र
A → B → C → A	A	चक्र में हेड शामिल
null	null	खाली लिस्ट

कोड से पहले साफ करो:

• सिंगली लिंक्ड? (हाँ।)
• अतिरिक्त जगह ओ(१)? (फ्लॉयड यही देता है। देखे गए नोड का हैशसेट आसान है पर ओ(एन) जगह लेता है।)
• नोड ऑब्जेक्ट लौटाओ, सिर्फ उसका डाटा मान नहीं।
• स्व-लूप की अनुमति? (हाँ।)

---

३. पहले सोचो (हैशसेट, फिर फ्लॉयड)

भोला तरीका: हर देखे गए नोड को याद रखो

हेड से चलो। हर Node संदर्भ को HashSet में डालो। अगर next पहले से सेट में है, वही लूप की शुरुआत है। अगर null मिला, लूप नहीं।

समय ओ(एन), जगह ओ(एन)। प्रोडक्शन में ठीक। इंटरव्यू में अक्सर अचर जगह वाला जवाब माँगते हैं।

फ्लॉयड: कछुआ और खरगोश (पहचानो, फिर ठिकाना लगाओ)

चरण १, मिलन-बिंदु खोजो।

• slow = head, fast = head
• लूप: slow = slow.next (१ कदम), fast = fast.next.next (२ कदम)
• अगर fast या fast.next null है, चक्र नहीं → null लौटाओ
• जब slow == fast, वे चक्र के अंदर मिले

चरण २, लूप की शुरुआत ढूँढो।

• slow (या fast) को मिलन-नोड पर छोड़ो
• दूसरा पॉइंटर वापस head पर रखो
• दोनों को एक-एक कदम चलाओ जब तक बराबर न हों
• वही नोड लूप की शुरुआत है

रीसेट क्यों चलता है (संक्षिप्त अंतर्ज्ञान)

मानो:

• μ = लूप शुरू होने से पहले के नोडों की संख्या (पहुँच-सड़क की लंबाई)
• λ = चक्र की लंबाई (अंडाकार)
• मिलन पर slow ने μ + a दूरी तय की है (प्रवेश से a कदम आगे, ० ≤ a < λ)

क्योंकि fast दोगुना तेज़ चलता है, उसने जो अतिरिक्त दूरी चली वह पूरे चक्करों की पूर्ण संख्या है। इससे साफ मॉड्यूलर संबंध बनता है: मिलन-बिंदु से चक्र घूमकर प्रवेश तक बची दूरी μ मॉड्यूलो λ के बराबर होती है।

इसलिए अगर एक पॉइंटर हेड पर लौटे और दोनों गति १ से μ कदम चलें, वे द्वार पर साथ पहुँचते हैं। कोड में μ या λ जानने की जरूरत नहीं। दोनों पॉइंटरों की समानता काफी है।

व्हाइटबोर्ड पर लंबी उपपत्ति की जरूरत नहीं। कहानी चाहिए: अंडाकार पर मिलो, फिर हेड और मिलन-बिंदु से बराबर चाल से दौड़ो, द्वार पर टकराओ।

---

४. जावा समाधान

/**
 * Returns the node at the start of the cycle, or null if the list is acyclic.
 * Floyd cycle detection: meet with tortoise/hare, then reset one pointer to head.
 */
Node findLoopStart(Node head) {
    if (head == null) {
        return null;
    }

    Node slow = head;
    Node fast = head;

    // Phase 1: do they ever meet?
    boolean met = false;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            met = true;
            break;
        }
    }

    if (!met) {
        return null; // no loop
    }

    // Phase 2: one pointer back to head; both step once until equal.
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow; // beginning of the loop
}

A → B → C → D → E → C का वॉकथ्रू:

चरण	घटना
शुरुआत	slow और fast दोनों A पर
कदम	खरगोश आगे निकलता है; दोनों आखिर C-D-E में घुसते हैं
मिलन	{C, D, E} में किसी नोड पर टकराते हैं (लंबाइयों पर निर्भर)
रीसेट	slow को A पर रखो, fast मिलन-नोड पर रहे
बराबर चाल	दोनों एक-एक नोड आगे
खत्म	दोनों C पर साथ खड़े

स्व-लूप A → A के लिए: चरण १ पहले ही कदम-जोड़े के बाद A पर मिलता है। चरण २ में slow = head भी A है, तो तुरंत slow == fast। A लौटाओ।

---

५. जटिलता तालिका

तरीका	समय	अतिरिक्त जगह	नोट
देखे गए नोडों का हैशसेट	ओ(एन)	ओ(एन)	आसान; दोबारा मिला पहला नोड ही शुरुआत
फ्लॉयड (कछुआ / खरगोश)	ओ(एन)	ओ(१)	दो चरण; जगह के लिए इंटरव्यू का पसंदीदा जवाब
नोड पर निशान (बदलने योग्य फील्ड)	ओ(एन)	ओ(१)	लिखने योग्य फील्ड चाहिए; साझा लिस्ट पर खराब

एन चक्र में दोबारा घुसने तक अलग नोडों की संख्या है (या सीधी लिस्ट में पूरी लंबाई)। फ्लॉयड सेट नहीं बनाता, इसलिए याददाश्त तंग हो या बफर मना हो तो यही जीतता है।

---

६. किनारे के केस और आम गलतियां

इंटरव्यूअर ये छूते हैं:

• कोई लूप नहीं → चरण १ में fast या fast.next से null। null लौटाओ। चरण २ में मत जाओ।
• एक नोड, बिना स्व-लूप (A → null) → पहली जाँच में fast.next खाली। लूप नहीं।
• एक नोड स्व-लूप (A → A) → शुरुआत A। रीसेट के बाद चरण २ तुरंत बराबरी।
• चक्र में हेड शामिल (A → B → C → A) → शुरुआत A।
• खाली लिस्ट → तुरंत null।
• दो नोड का चक्र (A → B → A) → वही एल्गोरिदम; खास केस मत बनाओ।
• लंबा उपसर्ग, छोटा लूप या उलटा → वही तरीका। समय एन में रैखिक रहता है।

आम गलतियां:

१. नोड की पहचान की जगह data मान की तुलना। दो नोड एक ही पूर्णांक रख सकते हैं पर एक ही वस्तु नहीं होते। संदर्भ पर == लगाओ। २. fast.next जाँचे बिना दोनों पॉइंटर आगे बढ़ाना। fast.next.next से पहले हमेशा fast != null && fast.next != null। ३. चरण २ भूलना। मिलन साबित करता है चक्र है। यह नहीं साबित करता कि मिलन-नोड ही शुरुआत है। ४. चरण २ में अलग-अलग गति। दोनों को एक कदम चलना है। रीसेट के बाद बराबर चाल पर ही गणित बैठता है। ५. चरण १ का मिलन-बिंदु ही उत्तर मान लेना। लगभग हमेशा गलत, जब तक लंबाइयों का संयोग न हो।

नल-सुरक्षित छोटा प्रवेश:

Node findLoopStartSafe(Node head) {
    return findLoopStart(head);
}

---

७. दोस्त को समझाने वाला सार

लूप डिटेक्शन पूछता है: अगर सिंगली लिंक्ड लिस्ट में चक्र है, तो वह किस नोड से शुरू होता है?

१. कछुआ एक कदम, खरगोश दो। खरगोश अंत पर गिरे तो चक्र नहीं। २. अगर मिलें, तो हेड पर या उसके बाद कहीं चक्र है। ३. एक पॉइंटर वापस हेड पर रखो। दोनों को एक-एक कदम चलाओ। जहाँ मिलें, वहीं लूप की शुरुआत। ४. क्यों: बिना-लूप वाले हिस्से की लंबाई और चक्र के चारों ओर का ऑफ़सेट रीसेट के बाद बराबर चाल पर संरेखित हो जाते हैं। μ या λ गिनने की जरूरत नहीं; अंडाकार का द्वार मिल जाता है। ५. खाली और सीधी लिस्ट पर null। एक नोड का स्व-लूप वही नोड लौटाता है।

तीस सेकंड में यह कह सको, दोनों चरण खींच सको, और "मिलन-बिंदु" को "लूप की शुरुआत" से गड़बड़ न करो, तो समस्या २.८ तुम्हारी है।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: इंटरसेक्शन
• अगला: थ्री इन वन