Two-Pointer Techniques - Learning Module

Loading content...

0/276

Cycle Detection — Floyd's Algorithm

When Data Structures Become Infinite

Consider this nightmare scenario: A production system starts consuming 100% CPU. Logs show a simple function that traverses a linked list is running endlessly. Users are affected, revenue is lost, and engineers scramble to find the cause.

The culprit? A cycle in the linked list. Somewhere, a node's next pointer points back to an earlier node, creating an infinite loop. The traversal function, expecting the list to end at null, runs forever.

This isn't a hypothetical—cycles in data structures cause real production incidents. They can arise from:

Bugs in insertion/deletion logic
Race conditions in concurrent modifications
Corrupted data deserialized from external sources
Deliberate attacks in untrusted input

Being able to detect cycles reliably and efficiently is a fundamental skill for any systems engineer.

What You Will Learn

By the end of this page, you will understand Floyd's Cycle Detection Algorithm in complete depth: why it works mathematically, how to implement it correctly, how to find the cycle's entry point, and how to calculate the cycle's length—all in O(n) time and O(1) space.

The Problem Statement

Formal Definition

Given a linked list, determine whether it contains a cycle. A cycle exists if some node in the list can be reached again by continuously following the next pointers.

Extended Problems

Beyond simple detection, we often need to answer:

Does a cycle exist? (Boolean answer)
Where does the cycle start? (Return the entry node)
How long is the cycle? (Return the cycle length λ)
How far is the cycle from the head? (Return the tail length μ)

Converting Mermaid diagram...

In the diagram above:

μ (mu) = 3: The distance from Head to the Cycle Entry (the 'tail' length)
λ (lambda) = 4: The cycle length (Entry → C1 → C2 → C3 → back to Entry)
Total nodes = 7: Three in the tail, four in the cycle

Understanding these parameters is crucial for the mathematical analysis of Floyd's algorithm.

Why Not Just Use a Hash Set?

A naive solution stores visited nodes in a hash set, checking each new node for duplicates. This works in O(n) time but requires O(n) space. Floyd's algorithm achieves the same time complexity with O(1) space—a significant improvement for memory-constrained environments or very large lists.

Floyd's Algorithm: The Core Idea

Floyd's Cycle Detection Algorithm uses the slow and fast pointer technique we learned in the previous page. The insight is beautifully simple:

If a cycle exists, slow and fast will eventually meet. If no cycle exists, fast will reach the end.

Here's why:

No cycle: Fast pointer moves faster and reaches null first. We terminate and report 'no cycle'.
Cycle exists: Once both pointers enter the cycle, they're on a circular track. Fast moves 2 nodes per step, slow moves 1 node. The gap between them decreases by 1 each step. Eventually, the gap becomes 0—they meet.

The elegance is that we don't need to know anything about the cycle's position or length in advance. The algorithm discovers it through the meeting.

cycle_detection.py
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
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def has_cycle(head: ListNode) -> bool:
    """
    Detect if a linked list has a cycle using Floyd's Algorithm.
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    
    Returns:
        True if cycle exists, False otherwise
    """
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    # Move slow by 1, fast by 2
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        # If they meet, cycle detected
        if slow == fast:
            return True
    
    # Fast reached end, no cycle
    return False

The Meeting Check Position

Notice the meeting check happens AFTER moving both pointers, not before. This is crucial—if we check at the start when both are at head, we'd falsely report a cycle. Always move first, then check for meeting.

Mathematical Proof of Correctness

To truly master Floyd's algorithm, we need to understand why it works mathematically. This proof is essential for understanding the cycle entry-point algorithm that follows.

Setup and Variables

Let's define our variables precisely:

μ (mu): Distance from head to cycle entry (the 'tail' length)
λ (lambda): The cycle length
k: Number of steps taken when slow and fast meet

The Key Equations

When slow and fast meet:

Slow has traveled: k nodes
Fast has traveled: 2k nodes (twice slow's distance)

Both are at the same position within the cycle. The difference in their distances (k nodes) must be a multiple of the cycle length λ:

2k - k = nλ (for some positive integer n)

This simplifies to: k = nλ

Meaning: Slow has traveled exactly n complete cycle lengths when they meet.

floyd_proof.txt
Floyd's Cycle Detection: Mathematical Proof
 
Given:
  - μ = distance from head to cycle entry (tail length)
  - λ = cycle length
  - Slow moves 1 node/step, Fast moves 2 nodes/step
 
At step k (when they meet):
  - Slow position: k nodes from head
  - Fast position: 2k nodes from head
 
Key insight: Both are at the same physical node.
  
Since they're at the same node in the cycle:
  Fast has traveled (2k - k) = k more nodes than Slow
  This extra distance k must be complete cycle rotations
  
  Therefore: k = nλ for some positive integer n
  
Minimum case (n = 1): k = λ
  They meet after slow travels exactly one cycle length
  This happens when μ ≤ λ
  
General case:
  Slow enters cycle after μ steps
  At that point, slow has (k - μ) more steps until meeting
  Meeting happens at position (k - μ) mod λ from cycle entry
  
  Since k = nλ:
    Meeting position = (nλ - μ) mod λ = (-μ) mod λ = (λ - μ mod λ)
  
  This position is deterministic given μ and λ

Why Meeting is Guaranteed

The crucial insight is that once both pointers are in the cycle, they must meet:

In the cycle, think of fast 'chasing' slow
Fast gains 1 position per step (moves 2, slow moves 1)
The gap decreases by 1 each step
Since the gap starts at most λ-1, meeting happens in at most λ-1 steps

Fast cannot 'skip over' slow because the gap changes by exactly 1 per step. It will always hit exactly 0.

Termination Guarantee

The algorithm terminates in O(n) steps:

If no cycle: fast reaches null in ⌈n/2⌉ steps
If cycle: meeting occurs within μ + λ ≤ n steps after slow enters the cycle

The Insight of Robert Floyd

Robert Floyd's brilliance was recognizing that the meeting point encodes information about the cycle structure. This observation leads directly to the cycle entry-point algorithm we'll see next. The mathematical relationship between meeting point and cycle entry is what makes O(1) space cycle characterization possible.

Finding the Cycle Entry Point

Detecting a cycle's existence is useful, but often we need to find where the cycle begins. This is crucial for:

Debugging (which node has the incorrect pointer?)
Recovery (how to break the cycle?)
Analysis (what data is in the cyclic portion?)

Floyds algorithm has an elegant extension that finds the cycle entry node in O(n) time and O(1) space.

The Algorithm

Run Floyd's detection to find the meeting point
Keep one pointer at the meeting point
Reset the other pointer to the head
Move both pointers one node at a time
Where they meet is the cycle entry

Why Does This Work?

This is where the math becomes beautiful. Let's prove why moving from head and from meeting point at equal speeds leads to the cycle entry.

The Proof

Let's use our variables:

μ = distance from head to cycle entry
λ = cycle length
M = meeting point (some position within the cycle)

When slow and fast meet at M:

Slow has traveled: μ + d (where d is distance from entry to M within cycle)
Fast has traveled: μ + d + nλ (some number of complete cycles extra)

Since fast travels twice as far: 2(μ + d) = μ + d + nλ

Simplifying: μ + d = nλ

Rearranging: μ = nλ - d

This is the key insight! The distance from head to entry (μ) equals nλ - d.

Now, if we start from M and walk (nλ - d) steps within the cycle:

We go (nλ - d) mod λ = (-d) mod λ = (λ - d) steps forward
But M is d steps past the entry
So (λ - d) steps from M brings us back to... the entry!

Meanwhile, walking μ = nλ - d steps from the head also reaches the entry.

Both paths meet at the cycle entry!

find_cycle_entry.py
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
def find_cycle_entry(head: ListNode) -> ListNode:
    """
    Find the entry point of a cycle in a linked list.
    
    Uses Floyd's algorithm extended with the entry-finding phase.
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    
    Returns:
        The node where the cycle begins, or None if no cycle exists
    """
    if not head or not head.next:
        return None
    
    # Phase 1: Detect cycle and find meeting point
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            # Cycle detected! Now find entry point
            break
    else:
        # No cycle found (fast reached end)
        return None
    
    # Phase 2: Find cycle entry
    # Reset one pointer to head, keep other at meeting point
    # Move both at same speed - they'll meet at entry
    entry_finder = head
    
    while entry_finder != slow:
        entry_finder = entry_finder.next
        slow = slow.next
    
    return entry_finder  # This is the cycle entry node

Edge Case: Entry is at Head

If the cycle starts at the head node (μ = 0), the algorithm still works. The entry-finder and slow both start at positions that are 0 steps from the cycle entry, so they 'meet' immediately at the entry point (the head). No special handling needed.

Calculating the Cycle Length

Once we've detected a cycle, finding its length is straightforward. From any point within the cycle, we count how many steps it takes to return to that same point.

The Algorithm

After finding the meeting point (any node in the cycle), fix one pointer there
Move the other pointer around the cycle, counting steps
When it returns to the fixed pointer, the count equals the cycle length λ

cycle_length.py
Python
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
def get_cycle_length(head: ListNode) -> int:
    """
    Find the length of the cycle in a linked list.
    
    Returns:
        The number of nodes in the cycle, or 0 if no cycle exists
    """
    if not head or not head.next:
        return 0
    
    # Phase 1: Detect cycle and find meeting point
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            # Cycle detected! slow is at meeting point
            break
    else:
        return 0  # No cycle
    
    # Phase 2: Count cycle length
    # Start from meeting point and count until we return
    count = 1
    current = slow.next
    
    while current != slow:
        count += 1
        current = current.next
    
    return count
 
 
def get_full_cycle_info(head: ListNode) -> dict:
    """
    Complete cycle analysis: detection, entry, and length.
    
    Returns a dictionary with:
        - has_cycle: bool
        - entry_node: ListNode or None
        - cycle_length: int
        - tail_length: int (distance from head to entry)
    """
    result = {
        "has_cycle": False,
        "entry_node": None,
        "cycle_length": 0,
        "tail_length": 0
    }
    
    if not head or not head.next:
        return result
    
    # Phase 1: Detect cycle
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            result["has_cycle"] = True
            break
    else:
        return result  # No cycle
    
    # Phase 2: Find entry point
    entry_finder = head
    tail_length = 0
    
    while entry_finder != slow:
        entry_finder = entry_finder.next
        slow = slow.next
        tail_length += 1
    
    result["entry_node"] = entry_finder
    result["tail_length"] = tail_length
    
    # Phase 3: Calculate cycle length
    cycle_length = 1
    current = entry_finder.next
    
    while current != entry_finder:
        cycle_length += 1
        current = current.next
    
    result["cycle_length"] = cycle_length
    
    return result

Complete Cycle Analysis Output
Property	Description	Complexity
has_cycle	Whether a cycle exists	O(n)
entry_node	The first node in the cycle	O(n)
cycle_length (λ)	Number of nodes in the cycle	O(λ) ⊆ O(n)
tail_length (μ)	Distance from head to entry	O(μ) ⊆ O(n)

Optimizing Multiple Queries

If you need all cycle properties, perform them in sequence with a single pass through detection. Don't restart from scratch for each query. The combined algorithm above is still O(n) time and O(1) space.

Visual Walkthrough

Let's trace through Floyd's algorithm step by step on a concrete example. This will solidify your understanding.

Example List: 1 → 2 → 3 → 4 → 5 → 3 (cycle back to node 3)

μ (tail length) = 2 (nodes 1, 2 before entry)
λ (cycle length) = 3 (nodes 3, 4, 5 form the cycle)
Entry node = 3

Phase 1: Cycle Detection
Step	Slow Position	Fast Position	Action
0	1	1	Initialize both at head
1	2	3	Slow +1, Fast +2
2	3 (entry)	5	Slow +1, Fast +2
3	4	4	Slow +1, Fast +2 (5→3→4)
—	4	4	MEETING! slow == fast

They meet at node 4, which is inside the cycle but not at the entry.

Phase 2: Finding Entry Point

Now reset one pointer to head, keep the other at the meeting point. Move both by 1.

Phase 2: Finding Cycle Entry
Step	From Head	From Meeting (4)	Action
0	1	4	Initialize pointers
1	2	5	Both +1
2	3	3	Both +1 — MEETING!

Both pointers meet at node 3, which is indeed the cycle entry point!

Verification with Math

μ = 2 (distance from head to entry)
Meeting point was node 4, which is d = 1 step past entry in cycle
λ = 3 (cycle length)
Our equation: μ = nλ - d → 2 = n(3) - 1 → 2 = 3n - 1 → n = 1 ✓

The math checks out: walking 2 steps from head reaches node 3 (entry). Walking 2 steps from node 4 in the cycle: 4→5→3, also reaches entry!

The Magic of Equal Distance

The algorithm works because μ (head to entry) and the remaining distance from the meeting point back to entry are equal (or differ by complete cycle lengths, which cancel out). This mathematical coincidence is what makes O(1) space entry-finding possible.

Practical Applications

Floyd's cycle detection extends far beyond linked lists. The core insight—using differential speeds to detect periodicity—applies to many domains.

Real-World Applications

•Data Structure Validation: Detect corruption in linked data structures (linked lists, graphs with pointer issues). Essential in debugging and testing.
•Infinite Loop Detection: In iterative algorithms that should converge, Floyd's can detect if the algorithm is stuck in a cycle of states.
•Finding Duplicate Numbers: The famous 'Find the Duplicate' problem (given n+1 numbers in range [1,n], find the duplicate) reduces to cycle detection!
•Pollard's Rho Algorithm: A factorization algorithm that uses cycle detection to find factors of large numbers. Key in cryptography and number theory.
•Random Number Generator Testing: Detect periodicity in pseudo-random number sequences. All PRNGs eventually cycle; Floyd's helps find when.
•Memory Leak Detection: Circular references in garbage-collected languages can sometimes be detected using cycle-finding variants.

The Find Duplicate Number Problem

This classic interview problem elegantly maps to cycle detection:

Given an array of n+1 integers where each integer is in [1, n], there's at least one duplicate. Find a duplicate.

The insight: Treat array indices as 'next pointers'. If nums = [1, 3, 4, 2, 2]:

Index 0 points to index nums[0] = 1
Index 1 points to index nums[1] = 3
Index 3 points to index nums[3] = 2
Index 2 points to index nums[2] = 4
Index 4 points to index nums[4] = 2 (back to index 2!)

The duplicate value (2) causes a cycle. Floyd's algorithm finds it!

find_duplicate.py
Python
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
def find_duplicate(nums: list[int]) -> int:
    """
    Find the duplicate number using Floyd's cycle detection.
    
    Treats array indices as pointers: nums[i] points to index nums[i].
    A duplicate means two indices point to the same place, creating a cycle.
    
    Time: O(n), Space: O(1)
    
    Example:
        nums = [1, 3, 4, 2, 2]
        Index chain: 0 → 1 → 3 → 2 → 4 → 2 → 4 → ... (cycle at 2,4)
        Duplicate = 2 (the entry point value)
    """
    # Phase 1: Find meeting point in cycle
    slow = nums[0]
    fast = nums[0]
    
    while True:
        slow = nums[slow]           # Move 1 step
        fast = nums[nums[fast]]     # Move 2 steps
        if slow == fast:
            break
    
    # Phase 2: Find cycle entry (the duplicate!)
    finder = nums[0]
    
    while finder != slow:
        finder = nums[finder]
        slow = nums[slow]
    
    return finder  # The duplicate number

Pattern Recognition

When you see problems about 'finding something that appears again' or 'detecting when a process revisits a state', think Floyd's Algorithm. The problem may not look like a linked list, but if you can define a 'next state' function, Floyd's might apply.

Common Pitfalls and Edge Cases

Floyd's algorithm is elegant but has several subtle points that cause bugs:

Common Mistakes

•Checking equality before moving: Starting with if slow == fast before any movement falsely detects a cycle at head.
•Using while-do instead of do-while logic: Language-dependent, but ensure at least one movement happens before checking.
•Forgetting null checks on fast.next: Causes crash when fast lands on the last node.
•Wrong pointer in Phase 2: Must reset one to HEAD, not to some other position. The other stays at meeting point.
•Returning meeting point as entry: Meeting point is usually NOT the cycle entry—you need Phase 2!

Edge Cases to Test

•Empty list (head = null): Should return false/null cleanly.
•Single node, no cycle: Node points to null. No cycle.
•Single node with self-cycle: Node points to itself. Cycle exists, entry is the node.
•Cycle starts at head (μ = 0): Whole list is the cycle. Entry is head.
•Very long tail, short cycle: μ >> λ. Algorithm still works.
•Very short tail, long cycle: μ << λ. Algorithm still works.

edge_case_tests.py
Python
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
def test_cycle_detection_edge_cases():
    """Test suite for Floyd's algorithm edge cases."""
    
    # Edge case 1: Empty list
    assert has_cycle(None) == False
    
    # Edge case 2: Single node, no cycle
    single = ListNode(1)
    assert has_cycle(single) == False
    
    # Edge case 3: Single node with self-cycle
    self_cycle = ListNode(1)
    self_cycle.next = self_cycle
    assert has_cycle(self_cycle) == True
    entry = find_cycle_entry(self_cycle)
    assert entry == self_cycle  # Entry is the node itself
    
    # Edge case 4: Two nodes, cycle
    n1 = ListNode(1)
    n2 = ListNode(2)
    n1.next = n2
    n2.next = n1  # Cycle back to n1
    assert has_cycle(n1) == True
    assert find_cycle_entry(n1) == n1
    
    # Edge case 5: Cycle in the middle
    # 1 → 2 → 3 → 4 → 5 → 3 (cycle at 3)
    nodes = [ListNode(i) for i in range(1, 6)]
    for i in range(4):
        nodes[i].next = nodes[i + 1]
    nodes[4].next = nodes[2]  # 5 → 3
    
    assert has_cycle(nodes[0]) == True
    assert find_cycle_entry(nodes[0]) == nodes[2]  # Entry at node 3
    assert get_cycle_length(nodes[0]) == 3  # Cycle: 3→4→5→3
    
    print("All edge case tests passed!")

Test Before Production

Always test cycle detection code with all edge cases before deploying. A bug in cycle detection can cause either false positives (breaking valid data) or false negatives (allowing infinite loops). Both are serious in production systems.

Algorithm Comparison: Floyd's vs Hash Set

While Floyd's algorithm is elegant, it's worth understanding when alternative approaches might be preferred.

Cycle Detection Approaches Comparison
Aspect	Floyd's Algorithm	Hash Set Approach
Time Complexity	O(n)	O(n)
Space Complexity	O(1)	O(n)
Finds Entry Point	Yes (with Phase 2)	Yes (first duplicate)
Finds Cycle Length	Yes (extra traversal)	No (need extra work)
Implementation Complexity	Medium (math needed)	Simple (just store and check)
Works Without Modification	Yes	Yes
Memory-Constrained Env	Excellent	Poor
Very Long Lists	Excellent	May cause OOM

When to Use Floyd's:

Memory is constrained
List is potentially very large
You need cycle length efficiently
Optimal solution is required (interviews)

When Hash Set Might Be Acceptable:

List is known to be small
Implementation time is limited
Code clarity is prioritized over space
You're debugging and need to record visited nodes anyway

hash_set_approach.py
Python
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
def find_cycle_entry_hashset(head: ListNode) -> ListNode:
    """
    Alternative: Find cycle entry using a hash set.
    
    Simpler logic but O(n) space.
    
    Time: O(n)
    Space: O(n)
    """
    seen = set()
    current = head
    
    while current:
        if current in seen:
            return current  # First repeated node = entry
        seen.add(current)
        current = current.next
    
    return None  # No cycle
 
 
# Trade-off illustration:
# 
# Floyd's: O(1) space, ~50 lines of careful code
# HashSet: O(n) space, ~10 lines of simple code
#
# For a list with 1 billion nodes:
#   Floyd's: ~40 bytes (few pointers)
#   HashSet: ~8-16 GB (storing all node references)
#
# The space difference becomes critical at scale.

Interview Expectations

In technical interviews, you're typically expected to know Floyd's algorithm for cycle detection. However, mentioning the hash set approach first as a 'naive' solution, then optimizing to Floyd's, demonstrates good problem-solving progression.

Summary: Mastering Cycle Detection

We've completed a rigorous exploration of Floyd's Cycle Detection Algorithm. Let's consolidate the key concepts:

Key Takeaways

•Floyd's algorithm detects cycles in O(n) time and O(1) space — Optimal for both complexity measures.
•The 2:1 speed ratio guarantees meeting in cycles — Fast gains 1 position per step; gap reaches 0 eventually.
•The meeting point encodes cycle structure — The mathematical relationship μ = nλ - d enables entry-finding.
•Phase 2 finds the cycle entry — Reset one pointer to head, move equally; meeting point is entry.
•Cycle length comes from traversing the cycle once — Simple counting from any cycle node.
•The algorithm extends beyond linked lists — Duplicate finding, PRNG testing, factorization all use this pattern.

What's Next

In the next page, we'll explore another fundamental application of the slow and fast pointer technique: finding the middle element in various scenarios. You'll learn different middle-finding variants, their use in divide-and-conquer algorithms, and how subtle implementation differences affect the result.

The cycle detection knowledge you've gained here forms the foundation for understanding why these pointer techniques are so powerful.

Page Complete

You now understand Floyd's Cycle Detection Algorithm at a deep level—the mathematics, the implementation, the edge cases, and the real-world applications. This is one of the most elegant algorithms in computer science, and you've mastered it.

Cycle Detection — Floyd's Algorithm

When Data Structures Become Infinite

This isn't a hypothetical—cycles in data structures cause real production incidents. They can arise from:

Bugs in insertion/deletion logic
Race conditions in concurrent modifications
Corrupted data deserialized from external sources
Deliberate attacks in untrusted input

Being able to detect cycles reliably and efficiently is a fundamental skill for any systems engineer.

What You Will Learn

The Problem Statement

Formal Definition

Given a linked list, determine whether it contains a cycle. A cycle exists if some node in the list can be reached again by continuously following the next pointers.

Extended Problems

Beyond simple detection, we often need to answer:

Does a cycle exist? (Boolean answer)
Where does the cycle start? (Return the entry node)
How long is the cycle? (Return the cycle length λ)
How far is the cycle from the head? (Return the tail length μ)

Converting Mermaid diagram...

In the diagram above:

μ (mu) = 3: The distance from Head to the Cycle Entry (the 'tail' length)
λ (lambda) = 4: The cycle length (Entry → C1 → C2 → C3 → back to Entry)
Total nodes = 7: Three in the tail, four in the cycle

Understanding these parameters is crucial for the mathematical analysis of Floyd's algorithm.

Why Not Just Use a Hash Set?

Floyd's Algorithm: The Core Idea

Floyd's Cycle Detection Algorithm uses the slow and fast pointer technique we learned in the previous page. The insight is beautifully simple:

If a cycle exists, slow and fast will eventually meet. If no cycle exists, fast will reach the end.

Here's why:

No cycle: Fast pointer moves faster and reaches null first. We terminate and report 'no cycle'.
Cycle exists: Once both pointers enter the cycle, they're on a circular track. Fast moves 2 nodes per step, slow moves 1 node. The gap between them decreases by 1 each step. Eventually, the gap becomes 0—they meet.

The elegance is that we don't need to know anything about the cycle's position or length in advance. The algorithm discovers it through the meeting.

cycle_detection.py
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
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def has_cycle(head: ListNode) -> bool:
    """
    Detect if a linked list has a cycle using Floyd's Algorithm.
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    
    Returns:
        True if cycle exists, False otherwise
    """
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    # Move slow by 1, fast by 2
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        # If they meet, cycle detected
        if slow == fast:
            return True
    
    # Fast reached end, no cycle
    return False

The Meeting Check Position

Mathematical Proof of Correctness

To truly master Floyd's algorithm, we need to understand why it works mathematically. This proof is essential for understanding the cycle entry-point algorithm that follows.

Setup and Variables

Let's define our variables precisely:

μ (mu): Distance from head to cycle entry (the 'tail' length)
λ (lambda): The cycle length
k: Number of steps taken when slow and fast meet

The Key Equations

When slow and fast meet:

Slow has traveled: k nodes
Fast has traveled: 2k nodes (twice slow's distance)

Both are at the same position within the cycle. The difference in their distances (k nodes) must be a multiple of the cycle length λ:

2k - k = nλ (for some positive integer n)

This simplifies to: k = nλ

Meaning: Slow has traveled exactly n complete cycle lengths when they meet.

floyd_proof.txt
Floyd's Cycle Detection: Mathematical Proof
 
Given:
  - μ = distance from head to cycle entry (tail length)
  - λ = cycle length
  - Slow moves 1 node/step, Fast moves 2 nodes/step
 
At step k (when they meet):
  - Slow position: k nodes from head
  - Fast position: 2k nodes from head
 
Key insight: Both are at the same physical node.
  
Since they're at the same node in the cycle:
  Fast has traveled (2k - k) = k more nodes than Slow
  This extra distance k must be complete cycle rotations
  
  Therefore: k = nλ for some positive integer n
  
Minimum case (n = 1): k = λ
  They meet after slow travels exactly one cycle length
  This happens when μ ≤ λ
  
General case:
  Slow enters cycle after μ steps
  At that point, slow has (k - μ) more steps until meeting
  Meeting happens at position (k - μ) mod λ from cycle entry
  
  Since k = nλ:
    Meeting position = (nλ - μ) mod λ = (-μ) mod λ = (λ - μ mod λ)
  
  This position is deterministic given μ and λ

Why Meeting is Guaranteed

The crucial insight is that once both pointers are in the cycle, they must meet:

In the cycle, think of fast 'chasing' slow
Fast gains 1 position per step (moves 2, slow moves 1)
The gap decreases by 1 each step
Since the gap starts at most λ-1, meeting happens in at most λ-1 steps

Fast cannot 'skip over' slow because the gap changes by exactly 1 per step. It will always hit exactly 0.

Termination Guarantee

The algorithm terminates in O(n) steps:

If no cycle: fast reaches null in ⌈n/2⌉ steps
If cycle: meeting occurs within μ + λ ≤ n steps after slow enters the cycle

The Insight of Robert Floyd

Finding the Cycle Entry Point

Detecting a cycle's existence is useful, but often we need to find where the cycle begins. This is crucial for:

Debugging (which node has the incorrect pointer?)
Recovery (how to break the cycle?)
Analysis (what data is in the cyclic portion?)

Floyds algorithm has an elegant extension that finds the cycle entry node in O(n) time and O(1) space.

The Algorithm

Run Floyd's detection to find the meeting point
Keep one pointer at the meeting point
Reset the other pointer to the head
Move both pointers one node at a time
Where they meet is the cycle entry

Why Does This Work?

This is where the math becomes beautiful. Let's prove why moving from head and from meeting point at equal speeds leads to the cycle entry.

The Proof

Let's use our variables:

μ = distance from head to cycle entry
λ = cycle length
M = meeting point (some position within the cycle)

When slow and fast meet at M:

Slow has traveled: μ + d (where d is distance from entry to M within cycle)
Fast has traveled: μ + d + nλ (some number of complete cycles extra)

Since fast travels twice as far: 2(μ + d) = μ + d + nλ

Simplifying: μ + d = nλ

Rearranging: μ = nλ - d

This is the key insight! The distance from head to entry (μ) equals nλ - d.

Now, if we start from M and walk (nλ - d) steps within the cycle:

We go (nλ - d) mod λ = (-d) mod λ = (λ - d) steps forward
But M is d steps past the entry
So (λ - d) steps from M brings us back to... the entry!

Meanwhile, walking μ = nλ - d steps from the head also reaches the entry.

Both paths meet at the cycle entry!

find_cycle_entry.py
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
def find_cycle_entry(head: ListNode) -> ListNode:
    """
    Find the entry point of a cycle in a linked list.
    
    Uses Floyd's algorithm extended with the entry-finding phase.
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    
    Returns:
        The node where the cycle begins, or None if no cycle exists
    """
    if not head or not head.next:
        return None
    
    # Phase 1: Detect cycle and find meeting point
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            # Cycle detected! Now find entry point
            break
    else:
        # No cycle found (fast reached end)
        return None
    
    # Phase 2: Find cycle entry
    # Reset one pointer to head, keep other at meeting point
    # Move both at same speed - they'll meet at entry
    entry_finder = head
    
    while entry_finder != slow:
        entry_finder = entry_finder.next
        slow = slow.next
    
    return entry_finder  # This is the cycle entry node

Edge Case: Entry is at Head

Calculating the Cycle Length

Once we've detected a cycle, finding its length is straightforward. From any point within the cycle, we count how many steps it takes to return to that same point.

The Algorithm

After finding the meeting point (any node in the cycle), fix one pointer there
Move the other pointer around the cycle, counting steps
When it returns to the fixed pointer, the count equals the cycle length λ

cycle_length.py
Python
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
def get_cycle_length(head: ListNode) -> int:
    """
    Find the length of the cycle in a linked list.
    
    Returns:
        The number of nodes in the cycle, or 0 if no cycle exists
    """
    if not head or not head.next:
        return 0
    
    # Phase 1: Detect cycle and find meeting point
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            # Cycle detected! slow is at meeting point
            break
    else:
        return 0  # No cycle
    
    # Phase 2: Count cycle length
    # Start from meeting point and count until we return
    count = 1
    current = slow.next
    
    while current != slow:
        count += 1
        current = current.next
    
    return count
 
 
def get_full_cycle_info(head: ListNode) -> dict:
    """
    Complete cycle analysis: detection, entry, and length.
    
    Returns a dictionary with:
        - has_cycle: bool
        - entry_node: ListNode or None
        - cycle_length: int
        - tail_length: int (distance from head to entry)
    """
    result = {
        "has_cycle": False,
        "entry_node": None,
        "cycle_length": 0,
        "tail_length": 0
    }
    
    if not head or not head.next:
        return result
    
    # Phase 1: Detect cycle
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            result["has_cycle"] = True
            break
    else:
        return result  # No cycle
    
    # Phase 2: Find entry point
    entry_finder = head
    tail_length = 0
    
    while entry_finder != slow:
        entry_finder = entry_finder.next
        slow = slow.next
        tail_length += 1
    
    result["entry_node"] = entry_finder
    result["tail_length"] = tail_length
    
    # Phase 3: Calculate cycle length
    cycle_length = 1
    current = entry_finder.next
    
    while current != entry_finder:
        cycle_length += 1
        current = current.next
    
    result["cycle_length"] = cycle_length
    
    return result

Complete Cycle Analysis Output
Property	Description	Complexity
has_cycle	Whether a cycle exists	O(n)
entry_node	The first node in the cycle	O(n)
cycle_length (λ)	Number of nodes in the cycle	O(λ) ⊆ O(n)
tail_length (μ)	Distance from head to entry	O(μ) ⊆ O(n)

Optimizing Multiple Queries

Visual Walkthrough

Let's trace through Floyd's algorithm step by step on a concrete example. This will solidify your understanding.

Example List: 1 → 2 → 3 → 4 → 5 → 3 (cycle back to node 3)

μ (tail length) = 2 (nodes 1, 2 before entry)
λ (cycle length) = 3 (nodes 3, 4, 5 form the cycle)
Entry node = 3

Phase 1: Cycle Detection
Step	Slow Position	Fast Position	Action
0	1	1	Initialize both at head
1	2	3	Slow +1, Fast +2
2	3 (entry)	5	Slow +1, Fast +2
3	4	4	Slow +1, Fast +2 (5→3→4)
—	4	4	MEETING! slow == fast

They meet at node 4, which is inside the cycle but not at the entry.

Phase 2: Finding Entry Point

Now reset one pointer to head, keep the other at the meeting point. Move both by 1.

Phase 2: Finding Cycle Entry
Step	From Head	From Meeting (4)	Action
0	1	4	Initialize pointers
1	2	5	Both +1
2	3	3	Both +1 — MEETING!

Both pointers meet at node 3, which is indeed the cycle entry point!

Verification with Math

μ = 2 (distance from head to entry)
Meeting point was node 4, which is d = 1 step past entry in cycle
λ = 3 (cycle length)
Our equation: μ = nλ - d → 2 = n(3) - 1 → 2 = 3n - 1 → n = 1 ✓

The math checks out: walking 2 steps from head reaches node 3 (entry). Walking 2 steps from node 4 in the cycle: 4→5→3, also reaches entry!

The Magic of Equal Distance

Practical Applications

Floyd's cycle detection extends far beyond linked lists. The core insight—using differential speeds to detect periodicity—applies to many domains.

Real-World Applications

•Data Structure Validation: Detect corruption in linked data structures (linked lists, graphs with pointer issues). Essential in debugging and testing.
•Infinite Loop Detection: In iterative algorithms that should converge, Floyd's can detect if the algorithm is stuck in a cycle of states.
•Finding Duplicate Numbers: The famous 'Find the Duplicate' problem (given n+1 numbers in range [1,n], find the duplicate) reduces to cycle detection!
•Pollard's Rho Algorithm: A factorization algorithm that uses cycle detection to find factors of large numbers. Key in cryptography and number theory.
•Random Number Generator Testing: Detect periodicity in pseudo-random number sequences. All PRNGs eventually cycle; Floyd's helps find when.
•Memory Leak Detection: Circular references in garbage-collected languages can sometimes be detected using cycle-finding variants.

The Find Duplicate Number Problem

This classic interview problem elegantly maps to cycle detection:

Given an array of n+1 integers where each integer is in [1, n], there's at least one duplicate. Find a duplicate.

The insight: Treat array indices as 'next pointers'. If nums = [1, 3, 4, 2, 2]:

Index 0 points to index nums[0] = 1
Index 1 points to index nums[1] = 3
Index 3 points to index nums[3] = 2
Index 2 points to index nums[2] = 4
Index 4 points to index nums[4] = 2 (back to index 2!)

The duplicate value (2) causes a cycle. Floyd's algorithm finds it!

find_duplicate.py
Python
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
def find_duplicate(nums: list[int]) -> int:
    """
    Find the duplicate number using Floyd's cycle detection.
    
    Treats array indices as pointers: nums[i] points to index nums[i].
    A duplicate means two indices point to the same place, creating a cycle.
    
    Time: O(n), Space: O(1)
    
    Example:
        nums = [1, 3, 4, 2, 2]
        Index chain: 0 → 1 → 3 → 2 → 4 → 2 → 4 → ... (cycle at 2,4)
        Duplicate = 2 (the entry point value)
    """
    # Phase 1: Find meeting point in cycle
    slow = nums[0]
    fast = nums[0]
    
    while True:
        slow = nums[slow]           # Move 1 step
        fast = nums[nums[fast]]     # Move 2 steps
        if slow == fast:
            break
    
    # Phase 2: Find cycle entry (the duplicate!)
    finder = nums[0]
    
    while finder != slow:
        finder = nums[finder]
        slow = nums[slow]
    
    return finder  # The duplicate number

Pattern Recognition

Common Pitfalls and Edge Cases

Floyd's algorithm is elegant but has several subtle points that cause bugs:

Common Mistakes

•Checking equality before moving: Starting with if slow == fast before any movement falsely detects a cycle at head.
•Using while-do instead of do-while logic: Language-dependent, but ensure at least one movement happens before checking.
•Forgetting null checks on fast.next: Causes crash when fast lands on the last node.
•Wrong pointer in Phase 2: Must reset one to HEAD, not to some other position. The other stays at meeting point.
•Returning meeting point as entry: Meeting point is usually NOT the cycle entry—you need Phase 2!

Edge Cases to Test

•Empty list (head = null): Should return false/null cleanly.
•Single node, no cycle: Node points to null. No cycle.
•Single node with self-cycle: Node points to itself. Cycle exists, entry is the node.
•Cycle starts at head (μ = 0): Whole list is the cycle. Entry is head.
•Very long tail, short cycle: μ >> λ. Algorithm still works.
•Very short tail, long cycle: μ << λ. Algorithm still works.

edge_case_tests.py
Python
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
def test_cycle_detection_edge_cases():
    """Test suite for Floyd's algorithm edge cases."""
    
    # Edge case 1: Empty list
    assert has_cycle(None) == False
    
    # Edge case 2: Single node, no cycle
    single = ListNode(1)
    assert has_cycle(single) == False
    
    # Edge case 3: Single node with self-cycle
    self_cycle = ListNode(1)
    self_cycle.next = self_cycle
    assert has_cycle(self_cycle) == True
    entry = find_cycle_entry(self_cycle)
    assert entry == self_cycle  # Entry is the node itself
    
    # Edge case 4: Two nodes, cycle
    n1 = ListNode(1)
    n2 = ListNode(2)
    n1.next = n2
    n2.next = n1  # Cycle back to n1
    assert has_cycle(n1) == True
    assert find_cycle_entry(n1) == n1
    
    # Edge case 5: Cycle in the middle
    # 1 → 2 → 3 → 4 → 5 → 3 (cycle at 3)
    nodes = [ListNode(i) for i in range(1, 6)]
    for i in range(4):
        nodes[i].next = nodes[i + 1]
    nodes[4].next = nodes[2]  # 5 → 3
    
    assert has_cycle(nodes[0]) == True
    assert find_cycle_entry(nodes[0]) == nodes[2]  # Entry at node 3
    assert get_cycle_length(nodes[0]) == 3  # Cycle: 3→4→5→3
    
    print("All edge case tests passed!")

Test Before Production

Algorithm Comparison: Floyd's vs Hash Set

While Floyd's algorithm is elegant, it's worth understanding when alternative approaches might be preferred.

Cycle Detection Approaches Comparison
Aspect	Floyd's Algorithm	Hash Set Approach
Time Complexity	O(n)	O(n)
Space Complexity	O(1)	O(n)
Finds Entry Point	Yes (with Phase 2)	Yes (first duplicate)
Finds Cycle Length	Yes (extra traversal)	No (need extra work)
Implementation Complexity	Medium (math needed)	Simple (just store and check)
Works Without Modification	Yes	Yes
Memory-Constrained Env	Excellent	Poor
Very Long Lists	Excellent	May cause OOM

When to Use Floyd's:

Memory is constrained
List is potentially very large
You need cycle length efficiently
Optimal solution is required (interviews)

When Hash Set Might Be Acceptable:

List is known to be small
Implementation time is limited
Code clarity is prioritized over space
You're debugging and need to record visited nodes anyway

hash_set_approach.py
Python
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
def find_cycle_entry_hashset(head: ListNode) -> ListNode:
    """
    Alternative: Find cycle entry using a hash set.
    
    Simpler logic but O(n) space.
    
    Time: O(n)
    Space: O(n)
    """
    seen = set()
    current = head
    
    while current:
        if current in seen:
            return current  # First repeated node = entry
        seen.add(current)
        current = current.next
    
    return None  # No cycle
 
 
# Trade-off illustration:
# 
# Floyd's: O(1) space, ~50 lines of careful code
# HashSet: O(n) space, ~10 lines of simple code
#
# For a list with 1 billion nodes:
#   Floyd's: ~40 bytes (few pointers)
#   HashSet: ~8-16 GB (storing all node references)
#
# The space difference becomes critical at scale.

Interview Expectations

Summary: Mastering Cycle Detection

We've completed a rigorous exploration of Floyd's Cycle Detection Algorithm. Let's consolidate the key concepts:

Key Takeaways

•Floyd's algorithm detects cycles in O(n) time and O(1) space — Optimal for both complexity measures.
•The 2:1 speed ratio guarantees meeting in cycles — Fast gains 1 position per step; gap reaches 0 eventually.
•The meeting point encodes cycle structure — The mathematical relationship μ = nλ - d enables entry-finding.
•Phase 2 finds the cycle entry — Reset one pointer to head, move equally; meeting point is entry.
•Cycle length comes from traversing the cycle once — Simple counting from any cycle node.
•The algorithm extends beyond linked lists — Duplicate finding, PRNG testing, factorization all use this pattern.

What's Next

The cycle detection knowledge you've gained here forms the foundation for understanding why these pointer techniques are so powerful.

Page Complete