एक रैखिक डेटा संरचना में चक्र का पता लगाने के लिए फ़्लॉइड साइकिल डिटेक्शन एल्गोरिदम

फ़्लॉइड साइकिल किसी एकल लिंक की गई सूची में चक्र का पता लगाने के लिए चक्र का पता लगाने वाले एल्गोरिदम में से एक है।

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

एल्गोरिदम

• हरे और कछुआ को सूची के शीर्ष नोड पर प्रारंभ करें।

• प्रारंभ में, खरगोश कछुआ से दुगनी गति से चलता है।

• खरगोश और कछुआ दोनों को ले जाएँ और पता करें कि क्या खरगोश लिंक की गई सूची के अंत तक पहुँचता है, वापस जाएँ क्योंकि सूची में कोई लूप नहीं है।

• नहीं तो हरे और कछुआ दोनों आगे बढ़ेंगे।

• यदि हरे और कछुआ एक ही नोड पर हैं, तो वापस लौटें क्योंकि हमें सूची चक्र मिल गया है।

• अन्यथा, चरण 2 से प्रारंभ करें।

उपरोक्त एल्गोरिथम के लिए स्यूडोकोड

tortoise := headNode
hare := headNode
foreach:
   if hare == end
      return 'There is No Loop Found.'
   hare := hare.next
   if hare == end
      return 'No Loop Found'
   hare = hare.next
   tortoise = tortoise.next
   if hare == tortoise
      return 'Cycle Detected'