Floyd Cycle Detection Algorithm สำหรับตรวจจับ Cycle ใน Linear Data Structure

Floyd Cycle Detection Algorithm

อัลกอริทึมตรวจจับ Cycle ใน Singly Linked List เรียกอีกชื่อว่า "Hare and Tortoise Algorithm" (กระต่ายและเต่า)

หลักการ

มี 2 Pointers (Hare และ Tortoise) เริ่มที่ Head:

• Hare วิ่งเร็วกว่า Tortoise 2 เท่า
• เมื่อ Hare ถึงปลายทาง Tortoise จะอยู่กลางทาง

ขั้นตอนอัลกอริทึม

1. Initialize Hare และ Tortoise ที่ Head Node
2. Hare วิ่ง 2 ก้าว Tortoise วิ่ง 1 ก้าว
3. ถ้า Hare ถึง End ของ Linked List → Return "No Loop"
4. มิฉะนั้น ทั้งคู่เดินต่อ
5. ถ้า Hare และ Tortoise อยู่ Node เดียวกัน → Return "Cycle Detected"
6. กลับไปขั้นตอน 2

Pseudocode

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'