मैंने कुछ साक्षात्कार प्रश्न ऑनलाइन पढ़े हैं कि अगर आप किसी लिंक्ड सूची में लूप रखते हैं तो आपको कैसे मिलेगा, और समाधान (फ्लॉइड के चक्र-खोज एल्गोरिदम) में दो पॉइंटर्स होंगे, एक दूसरे की तुलना में 2x तेज है , और जांचें कि क्या वे फिर से मिलते हैं।लिंक्ड लिस्ट लूप डिटेक्शन एल्गोरिदम
मेरा सवाल है: मैं सिर्फ एक सूचक तय क्यों नहीं कर सकता, बस दूसरे पॉइंटर को प्रत्येक चरण 1 कदम से आगे बढ़ाएं?
क्योंकि पहला (गैर-चलती) पॉइंटर लूप के भीतर नहीं हो सकता है, इसलिए पॉइंटर्स कभी नहीं मिलेंगे। (याद रखें कि एक लूप में सूची का केवल एक हिस्सा हो सकता है।)
यह साफ़ हो जाता है। धन्यवाद सब, क्योंकि मैं केवल एक सही उत्तर को चिह्नित कर सकता हूं, मैं जल्द से जल्द चिह्नित करूंगा। –
क्योंकि लूप में पहले पॉइंटर द्वारा इंगित तत्व शामिल नहीं हो सकता है।
उदाहरण के लिए, यदि पहला पॉइंटर तत्व 1 को इंगित करता है और लिंक की गई सूची में बाद में लूप होता है (1-> 2-> 3-> 4-> 2), तो आपका एल्गोरिदम इसका पता नहीं लगाएगा।
ने कुछ मामूली टाइपो हटा दिए हैं, इसलिए मैं आपको एक सप्ताह में 50+ अच्छी विवेक के साथ दे सकता हूं (क्योंकि आप बस कुछ सेकंडों द्वारा स्वीकार किए जाने से चूक गए हैं)। – DaveFar
@ डेवबॉल वाह। धन्यवाद। मुझे खुशी है कि आपने देखा। ;) काउबॉय के लिए – quasiverse
क्योंकि शायद पूरी तरह से लिंक्डलिस्ट लूप के भीतर नहीं है।
जब तक पहले सूचक जहां चरवाहे है, कोई पाश का पता चला है:
किसी लिंक किए गए सूची के लिए लैसो का पता लगाने एल्गोरिथ्म, आप दो संकेत की जरूरत है। लेकिन अगर आप इसे आगे बढ़ते हैं, तो अंत में यह लूप दर्ज करेगा।
बीटीडब्ल्यू, लासो ग्राफ सिद्धांत से टर्मिनस टेक्निकस है, काउबॉय नहीं है।
अगर कोई उत्सुक है, तो एल्गोरिदम का कुछ तेज़ संशोधन है: http://www.siafoo.net/algorithm/11 – Dave