Phát hiện vòng lặp trong linked list bằng thuật toán Floyd (rùa và thỏ) — vì sao chỉ cần O(1) bộ nhớ?

Ý tưởng: Dùng 2 con trỏ chạy khác tốc độ — slow đi 1 bước, fast đi 2 bước mỗi vòng. Nếu có vòng lặp, fast sẽ "đuổi kịp" và gặp slow; nếu không có thì fast chạm null.

Hình dung: hai người chạy trên đường đua tròn, người nhanh gấp đôi sẽ bắt kịp người chậm trong tối đa 1 vòng — khoảng cách thu hẹp 1 đơn vị mỗi bước nên chắc chắn gặp.

function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head
  while (fast && fast.next) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}

Độ phức tạp: thời gian O(n), bộ nhớ O(1) — không cần Set lưu node đã thăm (cách Set là O(n) bộ nhớ).

Mở rộng: muốn tìm node bắt đầu vòng lặp, sau khi gặp nhau cho 1 con trỏ về head rồi cho cả hai đi 1 bước/lần; điểm gặp lại là đầu vòng.