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ẽ gặp lại người chậm sau đúng 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.

Idea: Two pointers at different speeds — slow moves 1 step, fast moves 2 per iteration. With a cycle, fast catches up to slow; without one, fast hits null.

Picture it: two runners on a circular track, the one twice as fast laps the slower after one loop — the gap shrinks by 1 each step so a meeting is guaranteed.

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
}

Complexity: time O(n), space O(1) — no visited-Set needed (the Set approach is O(n) space).

Extension: to find the cycle's start, after they meet send one pointer back to head, then advance both 1 step at a time; their next meeting point is the cycle entrance.