LinkedList Cycle

Bài toán

Cho head của một danh sách liên kết. Hãy xác định xem danh sách này có chu trình (cycle) hay không. Chu trình xảy ra khi một node trong danh sách trỏ ngược lại một node đã xuất hiện trước đó, khiến việc duyệt danh sách không bao giờ kết thúc (infinite loop).

Phân Tích & Tiếp Cận

Cách 1: Hash Set

Duyệt qua danh sách, lưu từng node vào Set. Nếu gặp node nào đã có trong Set -> Có chu trình.

• Time: $O(n)$.
• Space: $O(n)$.

Cách 2: Floyd's Tortoise and Hare (Rùa và Thỏ) - O(1) Space

Đây là thuật toán tối ưu bộ nhớ. Ta dùng 2 con trỏ:

• Thỏ (Fast): Chạy nhanh (bước 2 bước).
• Rùa (Slow): Chạy chậm (bước 1 bước).

Logic: Nếu có chu trình (đường chạy vòng tròn), con Thỏ chạy nhanh chắc chắn sẽ đuổi kịp và gặp con Rùa tại một thời điểm nào đó (lap the slow runner). Nếu không có chu trình (đường thẳng), con Thỏ sẽ chạy đến đích (null) trước.

function hasCycle(head: ListNode | null): boolean {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow!.next;          // Rùa đi 1 bước
        fast = fast.next.next;      // Thỏ đi 2 bước

        if (slow === fast) {
            return true; // Gặp nhau => Có chu trình
        }
    }

    return false; // Thỏ tới đích => Không có chu trình
}

• Time Complexity: $O(n)$.
• Space Complexity: $O(1)$.

Pattern Nhận Diện

Thuật toán Fast & Slow Pointers (Tortoise and Hare) có thể giải quyết nhiều bài toán khác:

1. Tìm điểm bắt đầu của chu trình (Cycle Start - LeetCode 142).
2. Tìm điểm giữa của danh sách (Middle of Linked List - LeetCode 876).
3. Kiểm tra Palindrome Linked List.