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