Floyd's Cycle Detection - Tortoise and Hare

"Hai người chạy cùng vòng tròn, sớm muộn cũng gặp nhau." - HPN

Định nghĩa

Floyd's Cycle Detection (còn gọi là Tortoise and Hare) là thuật toán phát hiện cycle trong linked list hoặc sequence:

Slow pointer (Tortoise): Di chuyển 1 bước mỗi lần
Fast pointer (Hare): Di chuyển 2 bước mỗi lần
Nếu có cycle → Hai pointer sẽ gặp nhau

📘 Key Property

Space: O(1) - Không cần HashSet để track visited nodes!

Tại sao cần Floyd's Cycle?

Bài toán: Detect Cycle in Linked List

Approach	Time	Space
HashSet	O(N)	O(N)
Floyd's	O(N)	O(1)

🎯 MEMORY MATTERS

Với 1 triệu nodes:

HashSet: ~8 MB (1M × 8 bytes pointer)
Floyd's: ~16 bytes (2 pointers)

Mô hình hóa

Linked List với Cycle

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

Tortoise and Hare Movement

Step 0: T=1, H=1
        T
        1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → (back to 3)
        H

Step 1: T moves 1, H moves 2
            T
        1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
                H

Step 2: T moves 1, H moves 2
                T
        1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
                        H

Step 3:
                    T
        1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
                                H

Step 4:
                        T
        1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
                    H (H đã loop back!)

... Eventually they MEET inside the cycle!

The Math: Tại sao Guaranteed Meet?

Proof

Gọi:

$μ$ = Khoảng cách từ head đến cycle start
$λ$ = Độ dài cycle
$k$ = Số bước để gặp nhau

Khi slow pointer vào cycle (tại step $μ$ ):

Slow đã đi: $μ$ bước
Fast đã đi: $2 μ$ bước → Fast đang ở vị trí $(μ \mod λ)$ trong cycle

Relative speed: Fast "đuổi" slow với tốc độ 1 bước/iteration. → Fast sẽ đuổi kịp sau tối đa $λ$ iterations.

Guaranteed: Sau $O (μ + λ)$ = $O (N)$ bước, hai pointer gặp nhau.

Production Implementation

python

# HPN Engineering Standard
# Implementation: Floyd's Cycle Detection

from typing import Optional, TypeVar, Generic, Tuple
from dataclasses import dataclass


T = TypeVar('T')


@dataclass
class ListNode(Generic[T]):
    """Singly linked list node."""
    val: T
    next: Optional['ListNode[T]'] = None


class FloydCycleDetection:
    """
    Floyd's Cycle Detection Algorithm.
    
    Features:
        - O(N) time
        - O(1) space
        - Can find cycle start point
        - Can find cycle length
    
    Use Cases:
        - Linked list cycle detection
        - Find duplicate in array (as linked list)
        - Deadlock detection in resource graphs
    """
    
    @staticmethod
    def has_cycle(head: Optional[ListNode]) -> bool:
        """
        Detect if linked list has a cycle.
        
        Time: O(N)
        Space: O(1)
        
        Returns:
            True if cycle exists
        """
        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 == fast:
                return True
        
        return False
    
    @staticmethod
    def find_cycle_start(head: Optional[ListNode]) -> Optional[ListNode]:
        """
        Find the node where the cycle begins.
        
        Algorithm:
        1. Detect meeting point using fast/slow
        2. Reset one pointer to head
        3. Move both at speed 1 → they meet at cycle start
        
        Math: Distance from head to cycle start = 
              Distance from meeting point to cycle start
              
        Time: O(N)
        Space: O(1)
        
        Returns:
            Node where cycle starts, or None if no cycle
        """
        if not head or not head.next:
            return None
        
        # Phase 1: Detect cycle
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                break
        else:
            return None  # No cycle
        
        # Phase 2: Find cycle start
        # Reset one pointer to head
        slow = head
        
        while slow != fast:
            slow = slow.next
            fast = fast.next
        
        return slow
    
    @staticmethod
    def find_cycle_length(head: Optional[ListNode]) -> int:
        """
        Find the length of the cycle.
        
        Returns:
            Length of cycle, or 0 if no cycle
        """
        if not head or not head.next:
            return 0
        
        # Find meeting point
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                break
        else:
            return 0  # No cycle
        
        # Count cycle length
        length = 1
        current = slow.next
        
        while current != slow:
            length += 1
            current = current.next
        
        return length


def find_duplicate_number(nums: list[int]) -> int:
    """
    Find the duplicate number in array [1, n] with n+1 elements.
    
    This is a classic application of Floyd's algorithm!
    Treat array as linked list where nums[i] points to nums[nums[i]].
    
    Time: O(N)
    Space: O(1)
    
    Example:
        nums = [1, 3, 4, 2, 2]
        → Duplicate is 2
        
        As linked list:
        0 → 1 → 3 → 2 → 4
                    ↑   ↓
                    └───┘
    """
    # Phase 1: Find intersection point
    slow = nums[0]
    fast = nums[0]
    
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        
        if slow == fast:
            break
    
    # Phase 2: Find cycle entrance (= duplicate)
    slow = nums[0]
    
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow


# ============================================
# USAGE EXAMPLE
# ============================================
if __name__ == "__main__":
    # Create linked list with cycle
    # 1 → 2 → 3 → 4 → 5 → 6
    #         ↑           ↓
    #         └───────────┘
    
    nodes = [ListNode(i) for i in range(1, 7)]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    
    # Create cycle: 6 → 3
    nodes[5].next = nodes[2]
    
    detector = FloydCycleDetection()
    
    print("=== Cycle Detection ===")
    print(f"Has cycle: {detector.has_cycle(nodes[0])}")
    
    cycle_start = detector.find_cycle_start(nodes[0])
    print(f"Cycle starts at node with value: {cycle_start.val}")
    
    cycle_length = detector.find_cycle_length(nodes[0])
    print(f"Cycle length: {cycle_length}")
    
    # Find duplicate example
    print("\n=== Find Duplicate Number ===")
    nums = [1, 3, 4, 2, 2]
    duplicate = find_duplicate_number(nums)
    print(f"Array: {nums}")
    print(f"Duplicate: {duplicate}")
    
    # List without cycle
    print("\n=== No Cycle Case ===")
    simple_list = ListNode(1, ListNode(2, ListNode(3)))
    print(f"Has cycle: {detector.has_cycle(simple_list)}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217

Ứng dụng Thực tế

Use Case	Description
Linked List	Detect memory leak (circular reference)
Find Duplicate	LeetCode 287 - O(1) space solution
Deadlock Detection	Resource allocation graph cycle
State Machine	Detect infinite loops
Blockchain	Validate chain integrity

Brent's Algorithm (Variant)

Brent's algorithm là variant nhanh hơn Floyd's trong practice:

python

def brent_cycle_detection(head: ListNode) -> bool:
    """
    Brent's Algorithm - Faster cycle detection.
    
    Difference: Instead of slow moving every step,
    slow stays put until fast has moved 2^k steps.
    
    ~36% faster than Floyd's in practice.
    """
    if not head:
        return False
    
    slow = head
    fast = head.next
    power = 1
    length = 1
    
    while fast and fast != slow:
        if length == power:
            slow = fast
            power *= 2
            length = 0
        
        fast = fast.next
        length += 1
    
    return fast is not None

Anti-patterns

❌ TRÁNH

1. Dùng HashSet khi O(1) space required

python

# ❌ WRONG: O(N) space
def has_cycle(head):
    visited = set()
    while head:
        if head in visited:
            return True
        visited.add(head)
        head = head.next
    return False

# ✅ RIGHT: O(1) space với Floyd's

2. Quên check null pointers

python

# ❌ WRONG: Crash on empty list
fast = head.next  # NullPointerException!

# ✅ RIGHT: Always check
if not head or not head.next:
    return False

3. Nhầm meeting point với cycle start

python

# ❌ WRONG: Meeting point KHÔNG phải cycle start
if slow == fast:
    return slow  # Sai! Đây chỉ là meeting point

# ✅ RIGHT: Cần phase 2 để tìm cycle start
# (Reset one pointer, move both at speed 1)

So sánh Cycle Detection Algorithms

Algorithm	Time	Space	Notes
HashSet	O(N)	O(N)	Simple, more memory
Floyd's	O(N)	O(1)	Classic, interview favorite
Brent's	O(N)	O(1)	~36% faster in practice

💡 HPN's Rule

"Floyd's cho interview (dễ nhớ). Brent's cho production (nhanh hơn)."

Floyd's Cycle Detection - Tortoise and Hare ​

Định nghĩa ​

Tại sao cần Floyd's Cycle? ​

Bài toán: Detect Cycle in Linked List ​

Mô hình hóa ​

Linked List với Cycle ​

Tortoise and Hare Movement ​

The Math: Tại sao Guaranteed Meet? ​

Proof ​

Production Implementation ​

Ứng dụng Thực tế ​

Brent's Algorithm (Variant) ​

Anti-patterns ​

So sánh Cycle Detection Algorithms ​

Floyd's Cycle Detection - Tortoise and Hare

Định nghĩa

Tại sao cần Floyd's Cycle?

Bài toán: Detect Cycle in Linked List

Mô hình hóa

Linked List với Cycle

Tortoise and Hare Movement

The Math: Tại sao Guaranteed Meet?

Proof

Production Implementation

Ứng dụng Thực tế

Brent's Algorithm (Variant)

Anti-patterns

So sánh Cycle Detection Algorithms