हरे और कछुआ दृष्टिकोण

Question

के साथ लिंक्ड सूची में साइकिल का पता लगाना मैं समझता हूं कि एक लिंक्ड सूची में एक चक्र का पता लगाने के लिए मैं हरे और कछुए दृष्टिकोण का उपयोग कर सकता हूं, जिसमें 2 पॉइंटर्स (धीमी और तेज़ वाले) होते हैं। हालांकि, विकी और अन्य संसाधनों में पढ़ने के बाद, मुझे समझ में नहीं आ रहा है कि यह क्यों गारंटी है कि दो पॉइंटर्स ओ (एन) समय जटिलता में मिलेंगे।

Answer 1

यहां एक अनौपचारिक सबूत का प्रयास है।

चक्र का आकार कोई फर्क नहीं पड़ता। इसमें एक लंबी पूंछ हो सकती है, और अंत में एक लूप हो सकता है, या पूंछ के बिना शुरुआत से अंत तक एक लूप हो सकता है। चक्र के आकार के बावजूद, एक बात स्पष्ट है - कि कछुए सूचक संकेतक सूचक तक नहीं पकड़ सकता है। यदि दोनों कभी मिलते थे, तो खरगोश के सूचक को पीछे से कछुआ सूचक को पकड़ना पड़ता है।

स्थापना की है कि के साथ

, पर विचार दो possibilites:

1. खरगोश सूचक कछुआ सूचक के पीछे एक कदम है।
2. खरगोश सूचक कछुए सूचक के पीछे दो कदम है।

सभी दूरीें अंततः एक या दो तक कम हो जाएंगी।

कछुए पॉइंटर का मानना ​​है कि पहले हमेशा चलता है (यह भी दूसरी तरफ हो सकता है), फिर पहले मामले में, कछुआ सूचक एक कदम आगे ले जाता है। अब उनके बीच की दूरी 2 है। जब खरगोश सूचक अब 2 कदम उठाता है, तो वे उसी नोड पर उतरेंगे। आसान समझ के लिए चित्रित वही बात है। रास्ते में बहुत अधिक पाठ मिल सकता है।

 
♛ = hare 
♙ = tortoise 
X = both meet 

..♛♙... #1 - Initially, the hare is one step behind the tortoise. 
..♛.♙.. #2 - Now the tortoise takes one step. now hare is two steps behind. 
....X.. #3 - Next, the hare takes two steps and they meet! 

अब दूसरे मामले पर विचार जहां उनके बीच की दूरी 2. धीमी सूचक एक कदम आगे ले जाता है और उनके बीच की दूरी 3. अगला हो जाता है, तेजी से आगे बढ़ता सूचक दो कदम और उनके बीच की दूरी 1 तक कम हो जाता है जो पहले मामले के समान है जिसमें हमने पहले ही साबित कर दिया है कि वे एक और कदम में मिलेंगे। फिर, आसान समझ के लिए सचित्र।

 
.♛.♙... #1 - Initially, the hare is two steps behind the tortoise. 
.♛..♙.. #2 - Now the tortoise takes one step and they become three steps apart. 
...♛♙.. #3 - Next, the hare takes two steps which is identical to previous case. 

अब, क्यों इस एल्गोरिथ्म हे (एन) में होने की गारंटी है के रूप में, का उपयोग क्या हम पहले से ही स्थापित किया है कि खरगोश कछुआ को पूरा करेगा से पहले इसे आगे ले जाता है। जिसका मतलब है कि एक बार दोनों लूप के अंदर होते हैं, कछुआ एक और दौर पूरा करने से पहले, यह खरगोश से मिल जाएगा क्योंकि खरगोश तेजी से दोगुना हो जाता है। सबसे बुरे मामले में, लूप एन नोड्स के साथ एक सर्कल होगा। जबकि कछुए केवल एन चरणों में एक दौर पूरा कर सकता है, खरगोश उस समय दो राउंड पूरा कर सकता है। यहां तक ​​कि अगर खरगोश अपने पहले दौर में कछुए से चूक गया (जो यह होगा), यह निश्चित रूप से अपने दूसरे दौर में कछुए तक पहुंचने जा रहा है।

Answer 2

इसे इटरेटर्स A और B क्रमशः क्रमशः और दो लोगों द्वारा सूची में जाएं। Consdier वहाँ एक पाश मौजूद है। फिर उस समय जब A लूप में प्रवेश करता है, B पहले से ही इसके अंदर कहीं भी होगा। तो पाश की लंबाई K है, तो B इसके चारों ओर ]K/2[ चाल में, चलाता है, जिससे 2*]K/2[ पुनरावृत्तियों में ज्यादा से ज्यादा हम एक ऐसी स्थिति है जब B एक दूरी 1: B->A या 2: B->.->A में A पीछे दिखाई मिल जाएगा, और यह वें बारी B है '। इसके बाद, जाहिर है, वे 1 या 2 चालों में मिलेंगे। इसलिए, यदि लूप मौजूद है और P पर कुछ स्थिति से शुरू होता है, तो हम अधिकतर 2*P + 2*]K/2[ + 2 = O(N) पुनरावृत्तियों पर करते हैं।

Answer 3

//if you just want to check if there is a loop 

loop = false; 
item = head-of-list; 
while (item != nil) 
{ 
    if (item.next < 0) 
    { 
     loop = true; 
     break; 
    } 
    else 
    { 
     actual = item; 
     item = item.next; 
     actual.next = actual.next * -1; 
    } 
} 

return loop;