Làm thế nào để phát hiện chu trình bằng tortoise and hare của Floyd?

Question

Accepted Answer

**Phát hiện chu trình của Floyd** tìm một vòng lặp trong một dãy (như linked list) bằng cách dùng hai con trỏ di chuyển với tốc độ khác nhau. Nếu tồn tại một chu trình, con trỏ nhanh cuối cùng sẽ đuổi kịp và gặp con trỏ chậm. Nó dùng bộ nhớ phụ **O(1)**.

## Ý tưởng

Di chuyển con trỏ **chậm** một bước và con trỏ **nhanh** hai bước. Trong một chu trình, khoảng cách giữa chúng giảm đi một mỗi bước, nên chúng nhất định va vào nhau; nếu không có chu trình, con trỏ nhanh sẽ đến cuối.

## Ví dụ

```python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # +1 bước
        fast = fast.next.next       # +2 bước
        if slow is fast:            # các con trỏ gặp nhau -> có chu trình
            return True
    return False                    # fast tới cuối -> không có chu trình
```

## Độ phức tạp

- **Thời gian:** O(n). **Bộ nhớ:** O(1).

Cách dùng hash-set cũng hoạt động nhưng tốn O(n) bộ nhớ; thuật toán của Floyd dùng bộ nhớ hằng số.

## Khi nào dùng / những cạm bẫy

Dùng cho **phát hiện vòng lặp trong linked list**, tìm điểm bắt đầu của chu trình, và phát hiện chu trình trong các đồ thị hàm (functional graph, mỗi nút có một nút kế tiếp). Luôn bảo vệ `fast.next` để tránh tham chiếu null. Với đồ thị tổng quát, hãy dùng DFS với một recursion stack thay thế.

## Tại sao điều này quan trọng

Phát hiện chu trình là thiết yếu cho việc duyệt an toàn — một vòng lặp không được phát hiện đồng nghĩa với lặp vô hạn.

Thuật toán của Floyd là một ví dụ đẹp về việc giải một bài toán cần O(n) bộ nhớ chỉ trong O(1) bộ nhớ với một bất biến khôn ngoan.

Nó xuất hiện trong các bài phỏng vấn linked list và trong việc phát hiện vòng lặp vô hạn ở máy trạng thái và các dãy số.