ফ্লয়েড সাইকেল ডিটেকশন অ্যালগরিদম একটি লিনিয়ার ডেটা স্ট্রাকচারে চক্র সনাক্ত করতে

ফ্লয়েড সাইকেল হল সাইকেল ডিটেকশন অ্যালগরিদমগুলির মধ্যে একটি যা প্রদত্ত এককভাবে লিঙ্ক করা তালিকায় চক্রটিকে সনাক্ত করতে পারে৷

ফ্লয়েড সাইকেল অ্যালগরিদমে, আমাদের কাছে দুটি পয়েন্টার রয়েছে যা প্রাথমিকভাবে মাথার দিকে নির্দেশ করে। খরগোশ এবং কচ্ছপের গল্পে, খরগোশ কচ্ছপের চেয়ে দ্বিগুণ দ্রুত গতিতে চলে এবং যখনই খরগোশ পথের শেষ প্রান্তে পৌঁছায়, তখনই কচ্ছপটি পথের মাঝখানে পৌঁছে যায়।

অ্যালগরিদম

তালিকার প্রধান নোডে খরগোশ এবং কচ্ছপ শুরু করুন।
প্রাথমিকভাবে, খরগোশ কচ্ছপের চেয়ে দ্বিগুণ দ্রুত গতিতে চলে।
খরগোশ এবং কচ্ছপ উভয়কেই সরান এবং খরগোশ লিঙ্ক করা তালিকার শেষ প্রান্তে পৌঁছেছে কিনা তা খুঁজে বের করুন, তালিকায় কোন লুপ না থাকায় ফিরে আসুন।
অন্যথায়, খরগোশ এবং কচ্ছপ উভয়ই এগিয়ে যাবে।
যদি খরগোশ এবং কচ্ছপ একই নোডে থাকে, তাহলে ফিরে আসুন যেহেতু আমরা তালিকা চক্র খুঁজে পেয়েছি।
অন্যথায়, ধাপ 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'