Cấu trúc dữ liệu và Giải thuật Bài 31: Kỹ thuật Rùa và Thỏ (Floyd's Cycle-Finding Algorithm) để phát hiện chu trình.

Hãy tưởng tượng một đêm server Golang của bạn đột nhiên báo động đỏ: CPU bị vắt kiệt 100%, RAM không tăng nhưng request bị treo toàn bộ. Khi dump log ra kiểm tra, bạn phát hiện một hàm duyệt Danh sách liên kết đang kẹt trong một vòng lặp vĩnh cửu.

Đó là thảm họa mang tên Chu trình (Cycle). Nó xảy ra khi con trỏ Next của một Node cuối cùng không trỏ về nil như thiết kế chuẩn, mà vô tình trỏ ngược lại một Node nào đó ở phía trước. Hàm duyệt của bạn cứ thế đi vòng tròn không bao giờ thoát ra được. Làm sao để phát hiện cái bẫy chết người này với không gian bộ nhớ bằng 0?

1. Nỗi đau của tư duy "Đánh dấu" (Hash Map)

Phản xạ tự nhiên nhất để phát hiện một con đường có bị lặp lại hay không là "đánh dấu" những nơi mình đã đi qua.

Bạn có thể tạo một Hash Map (map[*Node]bool trong Golang) để lưu trữ địa chỉ bộ nhớ của các Node. Cứ mỗi lần bước sang Node mới, bạn kiểm tra xem địa chỉ này đã tồn tại trong Hash Map chưa. Nếu có, tức là bạn đã đi vào chu trình.

• Thời gian: $O(n)$

• Không gian (Bộ nhớ): $O(n)$. Đây chính là điểm yếu chí mạng. Nếu chuỗi có 10 triệu Node, Hash Map của bạn sẽ phình to khủng khiếp, tạo ra áp lực cực lớn lên bộ thu gom rác (Garbage Collector) của hệ thống.

2. Giải pháp vật lý: Kỹ thuật Rùa và Thỏ (Floyd's Cycle-Finding)

Năm 1967, Robert W. Floyd đã đưa ra một giải pháp cực kỳ thanh lịch dựa trên định luật vật lý về chuyển động trên một đường chạy vạch sẵn: Nếu hai vận động viên chạy trên một đường đua vòng tròn với vận tốc khác nhau, người chạy nhanh chắc chắn sẽ "bắt kịp" (lap) người chạy chậm.

Thuật toán sử dụng kỹ thuật Hai con trỏ cùng chiều (Fast & Slow Pointers) đã học ở Chương 3, nhưng với tốc độ khác biệt:

• Slow (Rùa): Khởi đầu từ Head, mỗi nhịp chỉ bước 1 bước (Slow = Slow.Next).

• Fast (Thỏ): Khởi đầu từ Head, mỗi nhịp nhảy 2 bước liên tiếp (Fast = Fast.Next.Next).

Logic vận hành:

1. Nếu danh sách KHÔNG có chu trình, con trỏ Fast (Thỏ) sẽ chạy thục mạng và tông vào tường nil ở cuối mảng rất nhanh. Thuật toán kết thúc an toàn.

2. Nếu danh sách CÓ chu trình, con trỏ Fast sẽ đi vào vòng lặp và cứ thế quay vòng. Con trỏ Slow cũng từ từ bò vào vòng lặp.

3. Vì Fast chạy nhanh gấp đôi Slow, khoảng cách giữa chúng trong vòng lặp sẽ bị rút ngắn đi 1 bước sau mỗi nhịp. Sớm muộn gì, con trỏ Fast cũng sẽ đâm sầm vào sau lưng con trỏ Slow (tức là Fast == Slow). Ngay tại khoảnh khắc chúng chập làm một, hệ thống sẽ gióng lên hồi chuông cảnh báo: Có chu trình!

3. Triển khai thuật toán bằng Golang

Đoạn mã sau giải quyết bài toán với thời gian $O(n)$ và không gian $O(1)$ tuyệt đối, không dùng đến Hash Map.

Go

type Node struct {
    Data int
    Next *Node
}

func hasCycle(head *Node) bool {
    // Nếu danh sách rỗng hoặc chỉ có 1 phần tử an toàn
    if head == nil || head.Next == nil {
        return false
    }

    slow := head
    fast := head

    // Điều kiện dừng: Thỏ đụng tường (nil)
    for fast != nil && fast.Next != nil {
        slow = slow.Next       // Rùa bò 1 bước
        fast = fast.Next.Next  // Thỏ nhảy 2 bước

        // Khoảnh khắc hội ngộ định mệnh
        if slow == fast {
            return true // Phát hiện chu trình!
        }
    }

    return false // Thỏ đến đích an toàn, không có vòng lặp
}

4. Tại sao lại là vận tốc 1 và 2?

Bạn có thể thắc mắc: "Tại sao không cho Thỏ nhảy 3, 4 hay 10 bước?"

Về mặt toán học, nếu Thỏ chạy với vận tốc $k$ ($k > 1$) và Rùa chạy với vận tốc $1$, chúng vẫn sẽ gặp nhau.

Tuy nhiên, chọn vận tốc k = 2 là cấu hình tối ưu nhất về mọi mặt:

1. Chống Null Pointer Exception: Nếu nhảy 3 bước, bạn phải kiểm tra fast.Next != nil VÀ fast.Next.Next != nil VÀ fast.Next.Next.Next != nil, code sẽ cực kỳ rườm rà.

2. Đảm bảo không bị "nhảy cóc" qua mặt nhau: Với vận tốc cách biệt đúng 1 đơn vị, khoảng cách giữa Thỏ và Rùa giảm đi chính xác 1 đơn vị mỗi nhịp. Chúng sẽ "va" vào nhau một cách hoàn hảo chứ không bao giờ có chuyện Thỏ nhảy xuyên qua mặt Rùa mà không kịp chạm.

5. Ứng dụng ở tầng Kiến trúc hệ thống (System Design)

Tư duy phát hiện chu trình bằng đa con trỏ là hạt nhân của nhiều cơ chế ngăn chặn lỗi nghiêm trọng:

• Phát hiện Deadlock trong Database: Trong các hệ quản trị cơ sở dữ liệu (như MySQL/PostgreSQL), nếu Transaction A chờ Transaction B nhả Lock, và B lại chờ A nhả Lock, một "Đồ thị chờ đợi" (Wait-for Graph) khép kín sẽ hình thành. Hệ thống dùng tư duy phát hiện chu trình để nhận diện vòng lặp này và ép một Transaction phải "chết" (Rollback) nhằm cứu toàn bộ database khỏi trạng thái treo cứng.

• Ngăn chặn Routing Loops trong Mạng (Networking): Khi các gói tin TCP/IP bị gửi vòng quanh giữa các Router bị cấu hình sai, chúng tạo ra hiện tượng bão mạng (Broadcast Storm). Dù các giao thức có cơ chế TTL (Time To Live), tư duy phát hiện chu trình vẫn được áp dụng trong các giao thức định tuyến (như BGP) để không bao giờ cho phép một đường dẫn khép kín được hình thành.

Kỹ thuật Rùa và Thỏ không chỉ dừng lại ở việc phát hiện có hay không một chu trình. Với một số phép biến đổi toán học nâng cao (Floyd's Phase 2), nó còn có thể chỉ ra chính xác Node nào là điểm bắt đầu gây ra chu trình đó. Tuy nhiên, để linh hoạt hơn trong việc di chuyển 2 chiều, các hệ thống thực tế thường nâng cấp Linked List đơn giản này thành một cấu trúc vững chãi hơn.