Algos 101, Bài 2 Thuật toán rùa và thỏ trong bài toán tìm chu trình

Hãy tưởng tượng bạn đang chạy trên một đường chạy hình tròn. Nếu một vận động viên khác chạy nhanh gấp đôi bạn, họ chắc chắn sẽ bắt kịp và vượt bạn sau một số vòng chạy. Ý tưởng vật lý trực quan này chính là nền tảng của giải thuật Phát hiện chu trình của Floyd (hay còn gọi là thuật toán Rùa và Thỏ - Tortoise and Hare), một kỹ thuật kinh điển trong cấu trúc dữ liệu và giải thuật dùng để kiểm tra xem một danh sách liên kết (Linked List) có bị lặp vô hạn hay không.

Trong bài viết này, chúng ta sẽ cùng phân tích bài toán phát hiện chu trình, xây dựng tư duy từ cách tiếp cận thô sơ đến giải pháp tối ưu, trực quan hóa từng bước dịch chuyển con trỏ, và cài đặt mã nguồn bằng Python.

---

📖 Yêu cầu & Ràng buộc bài toán

Cho đầu của một danh sách liên kết (head), hãy xác định xem danh sách này có chứa chu trình hay không. Một chu trình xảy ra nếu có một nút bất kỳ trong danh sách có thể được truy cập lại bằng cách liên tục đi theo con trỏ next.

Ví dụ 1:

Input: head = [3, 2, 0, -4], pos = 1 (nút cuối trỏ ngược về nút có giá trị 2)
Output: True
Giải thích: Danh sách có một chu trình khi nút cuối cùng trỏ ngược lại nút thứ hai.

Các ràng buộc:

• Số lượng nút trong danh sách nằm trong khoảng \([0, 10^4]\).
• \(-10^5 \le Node.val \le 10^5\)
• Độ phức tạp thời gian mục tiêu: $O(N)$
• Độ phức tạp không gian mục tiêu: $O(1)$ auxiliary space (bộ nhớ phụ trợ hằng số)

---

💡 Ý tưởng thuật toán: Từ Thô sơ đến Tối ưu

1. Giải pháp thô sơ: Sử dụng Hash Set (Lưu vết các nút đã đi qua)

Cách đơn giản nhất là duyệt qua danh sách và lưu trữ địa chỉ bộ nhớ (reference) của mỗi nút vào một tập hợp (Hash Set). Nếu gặp một nút đã tồn tại trong tập hợp này, điều đó chứng tỏ có chu trình.

• Độ phức tạp thời gian: $O(N)$ vì chúng ta chỉ duyệt qua mỗi nút tối đa một lần.
• Độ phức tạp không gian: $O(N)$ vì trong trường hợp xấu nhất (không có chu trình), chúng ta phải lưu toàn bộ $N$ nút vào tập hợp.

Tại sao cách này chưa tối ưu? Yêu cầu của bài toán là tối ưu bộ nhớ phụ trợ ở mức hằng số $O(1)$. Việc sử dụng Hash Set có kích thước tăng dần theo số lượng phần tử $N$ đã vi phạm ràng buộc này.

2. Giải pháp tối ưu: Hai con trỏ Rùa và Thỏ (Tortoise & Hare)

Để đạt được độ phức tạp không gian $O(1)$, chúng ta sử dụng hai con trỏ di chuyển với tốc độ khác nhau:

• Con trỏ Chậm (Rùa - slow): Di chuyển 1 bước mỗi lần.
• Con trỏ Nhanh (Thỏ - fast): Di chuyển 2 bước mỗi lần.

Nếu danh sách không có chu trình, con trỏ fast sẽ sớm chạm tới điểm cuối danh sách (None). Ngược lại, nếu có chu trình, con trỏ fast sẽ đi vào vòng lặp trước. Vì khoảng cách giữa fast và slow giảm đi 1 nút sau mỗi lượt di chuyển, hai con trỏ chắc chắn sẽ gặp nhau ở một nút nào đó trong chu trình.

---

🚶‍♂️ Minh họa từng bước chạy (State Walkthrough)

Hãy thử chạy tay (trace) thuật toán với danh sách liên kết có chu trình: [3, 2, 0, -4] trong đó nút -4 trỏ ngược lại nút 2 (chỉ số 1).

Bước	Giá trị con trỏ Chậm (slow)	Giá trị con trỏ Nhanh (fast)	Khoảng cách (số nút giữa hai con trỏ)	Ghi chú
0	3 (Nút đầu)	0 (Nút thứ 3)	2 nút	Khởi tạo
1	2	2 (Vòng ngược lại nút thứ 2)	0 nút	Gặp nhau! Phát hiện chu trình.

Vì slow == fast, thuật toán lập tức trả về True.

---

🛠️ Cài đặt Python

Dưới đây là mã nguồn Python sạch và chuẩn của giải thuật Tortoise and Hare:

from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional['ListNode'] = None):
        self.val = val
        self.next = next

def has_cycle(head: Optional[ListNode]) -> bool:
    """
    Kiểm tra danh sách liên kết đơn có chứa chu trình hay không.
    
    Time Complexity: O(N)
    Space Complexity: O(1)
    """
    if not head or not head.next:
        return False
    
    slow = head
    fast = head.next.next
    
    while fast and fast.next:
        if slow == fast:
            return True
        fast = fast.next.next
        slow = slow.next
        
    return False

---

📊 Phân tích độ phức tạp

• Độ phức tạp thời gian: $O(N)$
  • Không có chu trình: Con trỏ fast sẽ duyệt qua danh sách kích thước $N$ trong khoảng \(N/2\) bước. Vì vậy thời gian là $O(N)$.
  • Có chu trình: Giả sử đoạn thẳng ngoài chu trình có độ dài $L$ và vòng tròn chu trình có độ dài $C$. Con trỏ slow mất $L$ bước để đi vào chu trình. Khi cả hai đã ở trong chu trình, khoảng cách xa nhất giữa chúng là $C$. Do khoảng cách giảm đi 1 ở mỗi lượt, chúng sẽ gặp nhau sau tối đa $C$ bước. Tổng số bước là \(L + C \le N\), tương đương độ phức tạp $O(N)$.
• Độ phức tạp không gian bộ nhớ: $O(1)$
  • Chúng ta chỉ khởi tạo thêm hai biến tham chiếu slow và fast, bộ nhớ tiêu thụ cố định không đổi bất kể kích thước danh sách liên kết đầu vào.

---

🧠 Bài học rút ra

• Kỹ thuật Hai con trỏ nhanh & chậm (Fast & Slow Pointers) cực kỳ linh hoạt. Bên cạnh việc phát hiện chu trình, nó còn được dùng để tìm điểm chính giữa danh sách liên kết đơn hoặc tìm nút bắt đầu của chu trình đó.
• Phép toán đồng dư (modular arithmetic) đảm bảo hai vật thể chuyển động tuần hoàn trên một vòng khép kín với tốc độ khác nhau chắc chắn sẽ có lúc giao nhau.

Bạn đã từng áp dụng mô hình Rùa và Thỏ này trong các buổi phỏng vấn của mình chưa? Hãy để lại bình luận chia sẻ bên dưới nhé!