Floyd's Cycle Detection — Rùa và Thỏ

Một ngày, hệ thống monitoring báo rằng garbage collector của JVM không giải phóng được bộ nhớ — heap usage tăng liên tục cho đến khi OutOfMemoryError. Nguyên nhân: một linked list trong cache layer bị tạo vòng lặp do bug logic, khiến GC không bao giờ thu hồi được các node. Để phát hiện vòng lặp như vậy mà không tiêu thêm bộ nhớ, Robert W. Floyd đã đề xuất thuật toán hai con trỏ nổi tiếng: Tortoise and Hare.

Thuật toán chỉ cần 2 con trỏ — một chạy chậm (rùa, 1 bước/lần), một chạy nhanh (thỏ, 2 bước/lần). Nếu có vòng lặp, chúng chắc chắn gặp nhau. Space complexity: $O (1)$ thay vì $O (N)$ nếu dùng HashSet. Với 1 triệu node, đó là sự khác biệt giữa 16 bytes và 8 MB.

Ngoài linked list, Floyd's Cycle áp dụng cho bất kỳ hệ thống nào có state transition: deadlock detection trong resource graph, tìm phần tử trùng trong mảng (LeetCode 287), hay phát hiện infinite loop trong state machine.

Bức tranh tư duy

Hình dung sân vận động Mỹ Đình với đường chạy 400m hình oval. Một vận động viên chạy 1 vòng/phút (rùa), người kia chạy 2 vòng/phút (thỏ). Cả hai xuất phát cùng lúc từ vạch xuất phát.

Sau 1 phút: rùa ở vị trí 400m (1 vòng), thỏ ở 800m (2 vòng). Thỏ đã bỏ xa rùa 1 vòng. Nhưng vì đường tròn, thỏ thực tế đang ngay sau lưng rùa, đuổi kịp 1 vòng mỗi phút. Chắc chắn sẽ gặp nhau.

Nếu đường chạy không phải vòng tròn (chạy thẳng ra biển): thỏ chạy mãi xa dần, không bao giờ gặp rùa. → Không có cycle.

text

Linked list có vòng:

    1 → 2 → 3 → 4 → 5
              ↑       ↓
              8 ← 7 ← 6

Bước 0: Rùa = 1,  Thỏ = 1
Bước 1: Rùa = 2,  Thỏ = 3
Bước 2: Rùa = 3,  Thỏ = 5
Bước 3: Rùa = 4,  Thỏ = 7
Bước 4: Rùa = 5,  Thỏ = 3  (thỏ đã loop!)
Bước 5: Rùa = 6,  Thỏ = 5
Bước 6: Rùa = 7,  Thỏ = 7  ← GẶP NHAU! Có cycle.

📌 Khi nào analogy không còn chính xác

Vận động viên trên sân vận động luôn gặp nhau sau đúng 1 vòng chênh lệch. Trong linked list, vị trí gặp nhau phụ thuộc vào khoảng cách từ head đến cycle entry ( $μ$ ) và độ dài cycle ( $λ$ ). Điểm gặp không phải cycle entry — cần thêm bước 2 (Phase 2) để tìm entry.

Cốt lõi kỹ thuật

Phase 1: Phát hiện cycle

Hai con trỏ xuất phát từ head. Rùa đi 1 bước, thỏ đi 2 bước. Nếu gặp nhau → có cycle. Nếu thỏ đến null → không có cycle.

C++PythonJavaGo

cpp

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode* head) {
    if (!head || !head->next) return false;

    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

python

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

def has_cycle(head: ListNode | None) -> bool:
    """Phát hiện cycle trong linked list — O(N) time, O(1) space."""
    if not head or not head.next:
        return False

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True

    return False

java

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;

    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

type ListNode struct {
    Val  int
    Next *ListNode
}

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

Phase 2: Tìm điểm bắt đầu cycle

Sau khi phát hiện cycle (slow == fast), reset một con trỏ về head, rồi cả hai cùng đi 1 bước/lần. Điểm gặp mới chính là cycle entry.

Chứng minh toán học: Gọi $μ$ = khoảng cách từ head đến cycle entry, $λ$ = độ dài cycle, $k$ = khoảng cách từ cycle entry đến meeting point.

Khi gặp nhau: slow đi $μ + k$ bước, fast đi $2 (μ + k)$ bước. Chênh lệch = $μ + k$ = bội số của $λ$ . Suy ra: từ meeting point đi thêm $μ$ bước = vòng tròn trở lại cycle entry. Từ head đi $μ$ bước cũng đến cycle entry. → Hai con trỏ gặp nhau tại entry.

C++PythonJavaGo

cpp

ListNode* findCycleStart(ListNode* head) {
    if (!head || !head->next) return nullptr;

    ListNode* slow = head;
    ListNode* fast = head;

    // Phase 1: Tìm meeting point
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (!fast || !fast->next) return nullptr;

    // Phase 2: Tìm cycle entry
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

python

def find_cycle_start(head: ListNode | None) -> ListNode | None:
    """Tìm node bắt đầu cycle — O(N) time, O(1) space."""
    if not head or not head.next:
        return None

    slow = fast = head

    # Phase 1: Phát hiện cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # Không có cycle

    # Phase 2: Tìm entry point
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next

    return slow

java

public ListNode findCycleStart(ListNode head) {
    if (head == null || head.next == null) return null;

    ListNode slow = head, fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    if (fast == null || fast.next == null) return null;

    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

func findCycleStart(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }

    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            break
        }
    }
    if fast == nil || fast.Next == nil {
        return nil
    }

    slow = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }
    return slow
}

Ứng dụng: Tìm phần tử trùng trong mảng

Mảng nums có n+1 phần tử, giá trị trong khoảng [1, n]. Chắc chắn có ít nhất 1 phần tử trùng. Coi nums[i] là con trỏ "next" → bài toán trở thành phát hiện cycle trong linked list ẩn.

C++PythonJavaGo

cpp

int findDuplicate(const vector<int>& nums) {
    int slow = nums[0], fast = nums[0];

    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

python

def find_duplicate(nums: list[int]) -> int:
    """Tìm phần tử trùng — O(N) time, O(1) space (LeetCode 287)."""
    slow = fast = nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

java

public int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[0];

    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

func findDuplicate(nums []int) int {
    slow, fast := nums[0], nums[0]

    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }

    slow = nums[0]
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }
    return slow
}

Thực chiến

Tình huống: Phát hiện deadlock trong Resource Allocation Graph

Bối cảnh: Hệ thống microservice có N service, mỗi service giữ lock trên resource và chờ resource khác. Cần phát hiện circular wait (deadlock) trong $O (1)$ space.

Mục tiêu: Model dependency graph và dùng Floyd's Cycle để phát hiện vòng chờ.

python

class DeadlockDetector:
    """Phát hiện deadlock dùng Floyd's Cycle trên resource graph."""

    def __init__(self) -> None:
        # waits_for[A] = B nghĩa là service A đang chờ resource mà B giữ
        self.waits_for: dict[str, str | None] = {}

    def set_waiting(self, service: str, blocked_by: str) -> None:
        self.waits_for[service] = blocked_by

    def release(self, service: str) -> None:
        self.waits_for[service] = None

    def detect_cycle_from(self, start: str) -> list[str] | None:
        """
        Phát hiện cycle bắt đầu từ service.
        Returns danh sách service trong cycle, hoặc None.
        """
        slow = start
        fast = start

        while True:
            # Slow đi 1 bước
            slow = self.waits_for.get(slow)
            if slow is None:
                return None

            # Fast đi 2 bước
            fast = self.waits_for.get(fast)
            if fast is None:
                return None
            fast = self.waits_for.get(fast)
            if fast is None:
                return None

            if slow == fast:
                break

        # Tìm cycle entry (Phase 2)
        slow = start
        while slow != fast:
            slow = self.waits_for[slow]
            fast = self.waits_for[fast]

        # Thu thập các service trong cycle
        cycle = [slow]
        current = self.waits_for[slow]
        while current != slow:
            cycle.append(current)
            current = self.waits_for[current]

        return cycle


# Ví dụ: A chờ B, B chờ C, C chờ A → deadlock
detector = DeadlockDetector()
detector.set_waiting("ServiceA", "ServiceB")
detector.set_waiting("ServiceB", "ServiceC")
detector.set_waiting("ServiceC", "ServiceA")

cycle = detector.detect_cycle_from("ServiceA")
# cycle = ["ServiceA", "ServiceB", "ServiceC"]

Phân tích:

Model waits-for graph dưới dạng linked list ẩn (mỗi node có đúng 1 "next")
$O (1)$ space thay vì DFS cần $O (N)$ visited set
Giới hạn: chỉ phát hiện cycle đi qua start node. Production cần gọi cho mọi active service

Tình huống: Phát hiện Infinite Loop trong State Machine

Bối cảnh: Workflow engine xử lý state transitions. Cấu hình sai có thể tạo state A → B → C → A → ... (infinite loop). Cần phát hiện trước khi execution chạy mãi.

python

def detect_infinite_loop(
    transition: dict[str, str],
    start_state: str,
    max_states: int
) -> str | None:
    """
    Phát hiện infinite loop trong state machine.
    Returns: state bắt đầu loop, hoặc None nếu terminates.
    """
    slow = start_state
    fast = start_state

    for _ in range(max_states):
        slow = transition.get(slow)
        if slow is None:
            return None  # Terminal state — không loop

        fast = transition.get(fast)
        if fast is None:
            return None
        fast = transition.get(fast)
        if fast is None:
            return None

        if slow == fast:
            # Tìm loop entry
            slow = start_state
            while slow != fast:
                slow = transition[slow]
                fast = transition[fast]
            return slow

    return None  # Không phát hiện trong max_states bước

Phân tích:

Functional iteration: state machine transition là hàm f: State → State, Floyd's detect cycle trong chuỗi $x, f (x), f (f (x)), . . .$
max_states là safety net — tránh chạy mãi nếu state space quá lớn

Sai lầm điển hình

❌ Sai lầm 1: Dùng HashSet khi O(1) space là yêu cầu

Vấn đề: Phỏng vấn yêu cầu $O (1)$ space nhưng vẫn dùng HashSet.

python

# SAI: O(N) space — không đạt yêu cầu O(1)
def has_cycle(head):
    visited = set()
    while head:
        if id(head) in visited:
            return True
        visited.add(id(head))
        head = head.next
    return False

Tại sao sai: Với 1 triệu node, HashSet chiếm ~8MB (mỗi entry ≈ 8 bytes pointer). Floyd's chỉ cần 16 bytes (2 con trỏ). Trong embedded system hoặc khi xử lý graph khổng lồ, $O (N)$ space không chấp nhận được.

python

# ĐÚNG: O(1) space với Floyd's — xem Phase 1 ở trên
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

❌ Sai lầm 2: Nhầm meeting point với cycle entry

Vấn đề: Trả về meeting point của Phase 1 như thể đó là cycle entry.

python

# SAI: Meeting point ≠ cycle entry
def find_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return slow  # SAI! Đây là meeting point, không phải entry
    return None

Tại sao sai: Meeting point phụ thuộc vào $μ$ (khoảng cách đến cycle) và $λ$ (độ dài cycle). Nó có thể nằm ở bất kỳ đâu trong cycle. Cần Phase 2 (reset 1 con trỏ về head, cả hai đi speed 1) để tìm entry chính xác.

python

# ĐÚNG: Phase 2 tìm cycle entry
def find_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None

    slow = head  # Reset về head
    while slow is not fast:
        slow = slow.next
        fast = fast.next  # Cả hai đi speed 1
    return slow  # Đây mới là cycle entry

❌ Sai lầm 3: Quên kiểm tra null pointer

Vấn đề: Không kiểm tra head, head.next, hoặc fast.next trước khi truy cập.

python

# SAI: NullPointerException khi list rỗng hoặc 1 node
def has_cycle(head):
    slow = head
    fast = head.next  # Crash nếu head = None!
    while slow != fast:
        slow = slow.next
        fast = fast.next.next  # Crash nếu fast.next = None!
    return True

Tại sao sai: Linked list rỗng (head = None) hoặc chỉ có 1 node không bao giờ có cycle. Phải kiểm tra trước khi dereference.

python

# ĐÚNG: Guard clause đầu tiên
def has_cycle(head):
    if not head or not head.next:
        return False
    slow = fast = head
    while fast and fast.next:  # Kiểm tra cả fast và fast.next
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Under the Hood

Hiệu năng

Thuật toán	Time	Space	Ghi chú
HashSet	$O (N)$	$O (N)$	Đơn giản nhất, tốn bộ nhớ
Floyd's	$O (N)$	$O (1)$	Kinh điển, phỏng vấn yêu thích
Brent's	$O (N)$	$O (1)$	~36% nhanh hơn Floyd's trong thực tế

Chính xác hơn: Floyd's chạy trong $O (μ + λ)$ bước, với $μ$ = khoảng cách đến cycle entry, $λ$ = độ dài cycle. Worst case $μ + λ = N$ .

Nội bộ triển khai

Tại sao fast đi 2 bước, không phải 3? Với tốc độ chênh lệch 1 bước/iteration, fast "đuổi" slow đúng 1 vị trí mỗi vòng. Đảm bảo gặp nhau sau tối đa $λ$ vòng. Nếu fast đi 3 bước (chênh 2), fast có thể "nhảy qua" slow → không gặp trong cycle có $λ$ lẻ. Tốc độ 2 là optimal.

Brent's Algorithm: Thay vì slow di chuyển liên tục, slow đứng yên. Fast đi $2^{k}$ bước, rồi slow nhảy đến vị trí fast. Lặp lại với $k + 1$ . Giảm ~36% số comparison trung bình vì slow không cần di chuyển.

CPU cache behavior: Floyd's trên linked list có cache miss rate cao do pointer chasing (mỗi node ở vị trí memory ngẫu nhiên). Trên array (bài toán find duplicate), cache locality tốt hơn nhiều vì array liên tục trong memory.

Trade-offs

Khi NÊN dùng Floyd's	Khi KHÔNG NÊN dùng
Linked list cycle detection	Graph cycle detection (DFS tốt hơn)
Space $O (1)$ là bắt buộc	Cần tìm tất cả cycle (không chỉ 1)
Functional iteration $f (x)$	Multi-branching graph (node có nhiều outgoing edge)
Phỏng vấn — đây là expected answer	Distributed system (cần global state)

Checklist ghi nhớ

✅ Checklist triển khai

Nhận diện bài toán

[ ] Đề bài có "detect cycle", "find duplicate", "infinite loop" → nghĩ Floyd's
[ ] Mỗi node/state có đúng 1 "next" (functional graph) → Floyd's áp dụng được
[ ] Yêu cầu O(1) space → Floyd's thay vì HashSet

Triển khai Phase 1 (detect)

[ ] Guard: kiểm tra head == null và head.next == null
[ ] Cả hai con trỏ xuất phát từ head
[ ] Vòng lặp: kiểm tra fast != null && fast.next != null
[ ] So sánh identity (is / == pointer), không phải value

Triển khai Phase 2 (find entry)

[ ] Reset một con trỏ về head (không phải cả hai)
[ ] Cả hai đi speed 1 cho đến khi gặp nhau
[ ] Điểm gặp = cycle entry

Production

[ ] Bài find duplicate: coi nums[i] là linked list pointer
[ ] Deadlock detection: model waits-for graph dạng functional
[ ] State machine: transition function là "next" pointer

Bài tập luyện tập

Bài 1: Tìm độ dài cycle — Foundation

Đề bài: Cho linked list có cycle, tìm độ dài cycle (số node trong vòng).

🧠 Quiz

Câu hỏi kiểm tra: Sau khi Phase 1 tìm được meeting point, cách đúng để tìm cycle length là gì?

[ ] A. Đếm từ head đến meeting point
[x] B. Từ meeting point, đi tiếp 1 bước/lần đến khi quay lại meeting point
[ ] C. Tính $2 \times$ (số bước của Phase 1)
[ ] D. Dùng Phase 2 rồi đếm từ entry đến entry Giải thích: Meeting point nằm trong cycle. Đi tiếp từ meeting point, đếm số bước cho đến khi quay lại đúng meeting point = cycle length. Đáp án C sai vì Phase 1 có thể chạy nhiều hơn 1 vòng cycle.

💡 Gợi ý

Sau Phase 1, bạn có meeting point (nằm trong cycle)
Từ meeting point, dùng 1 con trỏ đi tiếp và đếm bước

✅ Lời giải

python

def cycle_length(head: ListNode | None) -> int:
    if not head or not head.next:
        return 0

    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # Đếm cycle length
            length = 1
            current = slow.next
            while current is not slow:
                length += 1
                current = current.next
            return length

    return 0  # Không có cycle

Phân tích: Time O(N), Space O(1). Bước đếm chạy đúng $λ$ lần (1 vòng cycle).

Bài 2: Happy Number — Intermediate

Đề bài: Một số gọi là "happy number" nếu lặp đi lặp lại quá trình thay mỗi chữ số bằng bình phương của nó, cuối cùng đạt 1. Ví dụ: 19 → $1^{2} + 9^{2}$ = 82 → $8^{2} + 2^{2}$ = 68 → ... → 1. Nếu không bao giờ đạt 1, nó rơi vào vòng lặp vô hạn. Kiểm tra một số có phải happy number không.

🧠 Quiz

Câu hỏi kiểm tra: Tại sao có thể dùng Floyd's Cycle cho bài này?

[ ] A. Vì bài toán liên quan đến linked list
[x] B. Vì chuỗi giá trị f(n), f(f(n)), ... hoặc đạt 1 hoặc rơi vào cycle — đúng mô hình functional iteration
[ ] C. Vì cần O(N) space
[ ] D. Vì happy number luôn là số nguyên tố Giải thích: Hàm "tổng bình phương chữ số" là hàm f: ℤ⁺ → ℤ⁺. Chuỗi n, f(n), f(f(n))... chắc chắn đi vào cycle (vì tập giá trị hữu hạn) hoặc đạt 1 (cycle ở 1 → 1). Floyd's phát hiện cycle trong chuỗi functional iteration.

💡 Gợi ý

Hàm "tổng bình phương chữ số" là f(n) — coi như "next pointer"
Slow gọi f 1 lần, fast gọi f 2 lần
Nếu gặp nhau tại 1 → happy. Gặp nhau tại số khác → không happy.

✅ Lời giải

python

def is_happy(n: int) -> bool:
    def sum_of_squares(num: int) -> int:
        total = 0
        while num > 0:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total

    slow = n
    fast = sum_of_squares(n)

    while fast != 1 and slow != fast:
        slow = sum_of_squares(slow)
        fast = sum_of_squares(sum_of_squares(fast))

    return fast == 1

Phân tích: Time O(log N) (giá trị giảm nhanh về vùng hữu hạn), Space O(1). Không cần HashSet lưu visited numbers.

Bài 3: Tìm phần tử trùng — LeetCode 287 — Advanced

Đề bài: Cho mảng nums có n+1 phần tử, giá trị trong [1, n]. Tìm phần tử trùng duy nhất. Yêu cầu: O(N) time, O(1) space, không được sửa mảng.

💡 Gợi ý

Coi nums[i] là pointer: index i trỏ đến index nums[i]
Phần tử trùng = cycle entry (vì 2 index trỏ đến cùng giá trị)
Dùng Floyd's 2 phase như linked list cycle

✅ Lời giải

python

def find_duplicate(nums: list[int]) -> int:
    # Phase 1: Phát hiện cycle
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # Phase 2: Tìm cycle entry = phần tử trùng
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

Phân tích: Time O(N), Space O(1), không sửa mảng. Trick: index 0 luôn nằm ngoài cycle (vì giá trị trong [1,n], không ai trỏ về 0) → đảm bảo Phase 2 bắt đầu từ "head" ngoài cycle.

Liên kết học tiếp

Từ khóa glossary: Floyd's cycle detection, tortoise and hare, rùa và thỏ, cycle entry, meeting point, functional iteration, phát hiện vòng lặp, Brent's algorithm

Tìm kiếm liên quan: phát hiện cycle linked list, tìm phần tử trùng O(1) space, happy number, deadlock detection, thuật toán hai con trỏ

Floyd's Cycle Detection — Rùa và Thỏ ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Phase 1: Phát hiện cycle ​

Phase 2: Tìm điểm bắt đầu cycle ​

Ứng dụng: Tìm phần tử trùng trong mảng ​

Thực chiến ​

Tình huống: Phát hiện deadlock trong Resource Allocation Graph ​

Tình huống: Phát hiện Infinite Loop trong State Machine ​

Sai lầm điển hình ​

❌ Sai lầm 1: Dùng HashSet khi O(1) space là yêu cầu ​

❌ Sai lầm 2: Nhầm meeting point với cycle entry ​

❌ Sai lầm 3: Quên kiểm tra null pointer ​

Under the Hood ​

Hiệu năng ​

Nội bộ triển khai ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Tìm độ dài cycle — Foundation ​

Bài 2: Happy Number — Intermediate ​

Bài 3: Tìm phần tử trùng — LeetCode 287 — Advanced ​

Liên kết học tiếp ​

Floyd's Cycle Detection — Rùa và Thỏ

Bức tranh tư duy

Cốt lõi kỹ thuật

Phase 1: Phát hiện cycle

Phase 2: Tìm điểm bắt đầu cycle

Ứng dụng: Tìm phần tử trùng trong mảng

Thực chiến

Tình huống: Phát hiện deadlock trong Resource Allocation Graph

Tình huống: Phát hiện Infinite Loop trong State Machine

Sai lầm điển hình

❌ Sai lầm 1: Dùng HashSet khi O(1) space là yêu cầu

❌ Sai lầm 2: Nhầm meeting point với cycle entry

❌ Sai lầm 3: Quên kiểm tra null pointer

Under the Hood

Hiệu năng

Nội bộ triển khai

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Tìm độ dài cycle — Foundation

Bài 2: Happy Number — Intermediate

Bài 3: Tìm phần tử trùng — LeetCode 287 — Advanced

Liên kết học tiếp