Thuật toán Floyd Cycle Detection phát hiện chu trình trong cấu trúc dữ liệu tuyến tính

Floyd Cycle là thuật toán phát hiện chu trình (cycle) trong singly linked list.

Trong Floyd Cycle, có 2 con trỏ ban đầu trỏ head. Theo chuyện Thỏ (Hare) và Rùa (Tortoise): Thỏ chạy gấp 2 lần Rùa. Khi Thỏ đến cuối đường, Rùa ở giữa.

Thuật toán

• Khởi tạo Hare và Tortoise tại head node.
• Hare di chuyển gấp 2 lần Tortoise.
• Di chuyển cả hai, nếu Hare đến cuối linked list → return (không có loop).
• Ngược lại, cả hai tiến tiếp.
• Nếu Hare và Tortoise trùng nút → return (phát hiện cycle).
• Ngược lại, quay lại bước 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'