चक्रीय लिंक्ड लिस्ट एल्गोरिदम

Question

मुझे हाल ही में एक एल्गोरिदम विकसित करने के लिए एक नौकरी साक्षात्कार में पूछा गया है जो यह निर्धारित कर सकता है कि एक लिंक्ड सूची चक्रीय है या नहीं। चूंकि यह एक लिंक्ड सूची है, हम इसके आकार को नहीं जानते हैं। यह एक दोहरी लिंक वाली सूची है जिसमें प्रत्येक नोड 'अगली' और 'पिछली' पॉइंटर्स है। किसी नोड को किसी अन्य नोड से जोड़ा जा सकता है या इसे स्वयं से जोड़ा जा सकता है।

उस समय एकमात्र समाधान जो मैं आया था वह एक नोड लेने और लिंक की गई सूची के सभी नोड्स के साथ जांचना था। साक्षात्कारकर्ता को स्पष्ट रूप से इस विचार को पसंद नहीं आया क्योंकि यह एक इष्टतम समाधान नहीं है। बेहतर दृष्टिकोण क्या होगा?

Answer 1

सामान्य समाधान अलग-अलग दरों पर 2 पॉइंटर्स चलना है। यदि सूची का कुछ हिस्सा परिपत्र है तो वे अंततः बराबर होंगे। इस की तर्ज पर कुछ:

function boolean hasLoop(Node startNode){ 
    Node slowNode = startNode; 
    Node fastNode1 = startNode; 
    Node fastNode2 = startNode; 

    while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){ 
    if (slowNode == fastNode1 || slowNode == fastNode2) 
     return true; 

    slowNode = slowNode.next(); 
    } 
    return false; 
} 

Blatantly यहाँ से चोरी: http://ostermiller.org/find_loop_singly_linked_list.html

Answer 2

आप इस प्रकार का सामान्य पूरा परिपत्र सूची संभाल कर सकते हैं: जब तक आप के अंत तक पहुँचते पहला तत्व के माध्यम से जुड़े सूची के माध्यम से लूप सूची या जब तक आप पहले तत्व पर वापस नहीं आते।

लेकिन यदि आप उस मामले को संभालना चाहते हैं जहां सूची का एक हिस्सा परिपत्र है तो आपको समय-समय पर अपना पहला सूचक आगे बढ़ने की आवश्यकता है।

Answer 3

उसी तत्व पर इंगित दो पॉइंटर्स के साथ प्रारंभ करें। next पॉइंटर्स के बाद, सूची के माध्यम से एक पॉइंटर चलाएं। दूसरा previous पॉइंटर्स के बाद सूची में चलता है। यदि दो पॉइंटर्स मिलते हैं, तो सूची परिपत्र है। यदि आपको previous या next पॉइंटर NULL पर सेट किया गया है, तो आपको पता है कि सूची परिपत्र है।

Answer 4

जो आप खोज रहे हैं वह चक्र-खोज एल्गोरिदम है। एल्गोरिदम जोएल को संदर्भित किया जाता है जिसे या तो 'कछुआ और खरगोश' एल्गोरिदम या फ़्लॉइड के चक्र खोज एल्गोरिदम कहा जाता है। मैं दूसरा पसंद करता हूं क्योंकि ऐसा लगता है कि यह एक अच्छा डी & डी वर्तनी करेगा।

Wikpedia overview of cycle finding algorithms, नमूना कोड

Answer 5

[प्रश्न संपादित करें और इस विषय के साथ स्पष्ट करने के लिए है कि हम एक दोगुना लिंक्ड सूची में चक्र के लिए जाँच कर रहे हैं, की जाँच नहीं करता है, तो एक दोगुना लिंक्ड सूची केवल परिपत्र है, इसलिए भागों reworded कर दिया गया है इस पोस्ट के अप्रासंगिक हो सकता है।]

इसके प्रत्येक नोड होने 'अगले' और 'पिछला' संकेत के साथ एक दोगुना लिंक सूची।

डबली-लिंक्ड सूचियों को सामान्य रूप से सूची के सिर और पूंछ के साथ लागू किया जाता है जो इंगित करता है कि वे कहां समाप्त होते हैं।

[संपादित करें] जैसा कि बताया गया है, यह केवल तभी जांचता है जब सूची पूरी तरह से परिपत्र है, न कि इसमें चक्र हैं, लेकिन यह मूल प्रश्न का शब्द था। यदि सूची परिपत्र है, पूंछ-> अगला == सिर और/या सिर-> पिछला == पूंछ। यदि आपके पास पूंछ और सिर नोड दोनों तक पहुंच नहीं है और केवल उनमें से एक है लेकिन दोनों नहीं, तो यह जांचने के लिए पर्याप्त होना चाहिए कि क्या सिर-> prev! = NULL या tail-> अगला! = NULL।

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

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

[संपादित करें] मेरे दिमाग ने अब सूची में चक्रों का पता लगाने पर ध्यान केंद्रित किया है, यह निर्धारित करने के विरोध में कि एक लिंक्ड सूची गोलाकार है या नहीं।

हम तरह के मामले हैं: -> 2 < -> 3 < -> [2]

एक ही रास्ता मैं देख सकता हूँ कि हम चक्र का पता लगा सकते सभी तत्वों का ट्रैक रखने के लिए है हम अब तक चले गए और रास्ते में किसी भी मैच की तलाश में।

बेशक यह सस्ता हो सकता है। अगर हमें सूची नोड्स को संशोधित करने की अनुमति है, तो हम प्रत्येक नोड के साथ एक आसानी से ट्रैवर्स ध्वज रख सकते हैं जिसे हम सेट कर रहे हैं। अगर हम पहले से सेट इस झंडे के साथ एक नोड का सामना करते हैं, तो हमें एक चक्र मिला है। हालांकि, यह समांतरता के लिए अच्छा काम नहीं करेगा।

यहां प्रस्तावित एक समाधान है [जिसे मैंने दूसरे जवाब से चुरा लिया] जिसे "फ़्लॉइड साइकल-फाइंडिंग एल्गोरिदम" कहा जाता है। आइए इसे देखें (संशोधित करने के लिए इसे थोड़ा आसान बनाने के लिए संशोधित)।

function boolean hasLoop(Node startNode) 
{ 
    Node fastNode2 = startNode; 
    Node fastNode1 = startNode; 
    Node slowNode = startNode; 

    while (slowNode && (fastNode1 = fastNode2.next()) && (fastNode2 = fastNode1.next())) 
    { 
     if (slowNode == fastNode1 || slowNode == fastNode2) 
      return true; 
     slowNode = slowNode.next(); 
    } 
    return false; 
} 

यह मूल रूप से 1. के बजाय 3 iterators का उपयोग करना शामिल हम तरह के मामले देख सकते हैं:> 1- 2-> 3> 4> 5> 6 -> [2] केस:

सबसे पहले हम [1] से तेज़ इटरेटर [2] और दूसरे [3] या [1, 2, 3] के साथ शुरू करते हैं। हम रुकते हैं जब पहला इटरेटर दो सेकंड इटरेटर में से किसी एक से मेल खाता है।

हम आगे बढ़ते हैं [2, 4, 5] (पहला तेज़ इटेटरेटर दूसरे फास्ट इटरेटर के अगले नोड को पार करता है, और दूसरा तेज़ इटेटरेटर उसके बाद पहले तेज इटरेटर के अगले नोड को पार करता है)। फिर [3, 6, 2], और अंत में [4, 3, 4]।

याय, हमें एक मैच मिला है, और इस प्रकार 4 पुनरावृत्तियों में एक चक्र रखने के लिए सूची निर्धारित की है।

Answer 6

पॉइंटर मूल्यों का हैश रखें। हर बार जब आप नोड जाते हैं, तो उसका पॉइंटर है और इसे स्टोर करता है। यदि आप कभी भी उस स्थान पर जाते हैं जो पहले से ही संग्रहीत किया गया है, तो आप जानते हैं कि आपकी सूची परिपत्र है।

यदि आपकी हैश तालिका स्थिर है तो यह एक ओ (एन) एल्गोरिदम है।

Answer 7

एक और विकल्प यह है कि चूंकि सूची दोगुनी जुड़ी हुई है, इसलिए आप सूची को पार कर सकते हैं और जांच सकते हैं कि अगला पॉइंटर्स हमेशा मौजूदा नोड या शून्य है और सिर नहीं है।

- -*- \ 
    \ \ 
     \--- 

नोड पर * वहाँ केवल एक जिनमें से 2 आने वाले लिंक पिछले हो सकते हैं: विचार है कि यहाँ एक पाश या तो पूरी सूची धरना या कुछ इस तरह दिखाई चाहिए।

कुछ की तरह:

bool hasCycle(Node head){ 
    if(head->next == head) return true; 

    Node current = head -> next; 

    while(current != null && current->next != null) { 
     if(current == head || current->next->prev != current) 
      return true; 

     current = current->next; 
    } 
    return false; // since I've reached the end there can't be a cycle. 
} 

Answer 8

यह मानते हुए कि किसी को कहते हैं, "यहाँ एक सूची के एक सदस्य के लिए एक सूचक यह एक परिपत्र सूची का सदस्य है।?" तो आप पॉइंटर्स के लिए एक नोड को सूची के एक दिशा में सभी पहुंचने योग्य सदस्यों की जांच कर सकते हैं जिन्हें आपको पॉइंटर में पॉइंटर दिया गया था जो आपको दूर करना चाहिए। यदि आप में अगले दिशा में जाने का निर्णय लेते हैं तो आप next पॉइंटर्स देखें जो आपके द्वारा पहले दिए गए सूचक के बराबर हैं। यदि आप पिछला दिशा में जाने का विकल्प चुनते हैं तो आप prev पॉइंटर्स की तलाश करते हैं जो आपके द्वारा पहले दिए गए पॉइंटर के बराबर होते हैं। यदि आप किसी भी दिशा में NULL पॉइंटर तक पहुंचते हैं तो आपको अंत मिल गया है और पता है कि यह परिपत्र नहीं है।

आप एक ही समय में दोनों दिशाओं में जाकर और देख सकते हैं कि आप स्वयं में टक्कर डालते हैं, लेकिन यह अधिक जटिल हो जाता है और यह वास्तव में आपको कुछ भी बचा नहीं देता है। यहां तक ​​कि यदि आपने इसे बहु-कोर मशीन पर 2 धागे के साथ कार्यान्वित किया है तो भी आप साझा अस्थिर स्मृति तुलना से निपटेंगे, जो प्रदर्शन को मार देगा।

वैकल्पिक रूप से, यदि आप सूची में प्रत्येक नोड को चिह्नित कर सकते हैं तो आप यह निर्धारित करने का प्रयास कर सकते हैं कि अंत में खोजते समय आपके निशान की तलाश करके कोई चक्र था या नहीं। यदि आपको नोड में अपना निशान मिला तो आपको पता चलेगा कि आप वहां पहले थे। यदि आपको अपने अंकों में से एक पाया जाने से पहले आपको अंत मिल गया तो आपको पता चलेगा कि यह परिपत्र नहीं था। यह एक और धागे का काम एक ही समय में ऐसा करने की कोशिश नहीं कर रहा था, हालांकि, क्योंकि आप अपने अंक मिश्रित कर पाएंगे, लेकिन अन्य कार्यान्वयन काम नहीं करेगा अगर अन्य थ्रेड परीक्षण के साथ ही एक ही समय में सूची को पुन: व्यवस्थित कर रहे थे ।

Answer 9

आपको क्या चाहिए Floyd's cycle-finding algorithm। आप चक्र के चौराहे बिंदु को होमवर्क के रूप में ढूंढने के बारे में भी सोच सकते हैं।

Answer 10

यह अविश्वसनीय है कि जटिल समाधान कितने व्यापक हो सकते हैं।

bool is_circular(node* head) 
{ 
    node* p = head; 

    while (p != nullptr) { 
     p = p->next; 
     if (p == head) 
      return true; 
    } 

    return false; 
} 

Answer 11

यहाँ एक साफ दृष्टिकोण अगर एक लिंक्ड सूची में चक्र है (अगर यह चक्रीय है) फ्लोयड के एल्गोरिथ्म के आधार पर परीक्षण करने के लिए है:

यहाँ एक निरपेक्ष खोजने के लिए कि क्या एक लिंक्ड सूची परिपत्र है के लिए आवश्यक न्यूनतम है:

int HasCycle(Node* head) 
{ 
    Node *p1 = head; 
    Node *p2 = head; 

    while (p1 && p2) { 
     p1 = p1->next; 
     p2 = p2->next->next; 

     if (p1 == p2) 
      return 1; 
    } 
    return 0; 
} 

विचार, दो संकेत का उपयोग करना है दोनों head से शुरू, अलग अलग गति पर है कि अग्रिम। यदि वे एक दूसरे से मिलते हैं, तो यह हमारा संकेत है कि हमारी सूची में एक चक्र है, यदि नहीं, तो सूची चक्र-कम है।