Linked List Cycle Detection: Floyd's Algorithm

A cycle in a linked list means some node’s next pointer points back to an earlier node, creating a loop. If you naively traverse such a list looking for None, you will loop forever. Detecting and analyzing cycles is a fundamental linked list skill, and Floyd’s algorithm does it with O(1) space.

Why Cycles Happen

Cycles are almost always bugs — they happen when:

• A node’s next is accidentally set to an earlier node during insertion or reversal
• Circular linked lists are used intentionally but a function expecting a linear list receives one
• Memory corruption or incorrect pointer manipulation occurs in low-level code

If you try to traverse a list with a cycle, your program hangs. If you try to find the length, you get infinity. Detecting cycles is essential for defensive programming.

The Brute Force Approach: Hash Set

The simplest way to detect a cycle is to store every visited node in a set:

def has_cycle_hashset(head):
    """Detect cycle using a hash set. O(n) time, O(n) space."""
    visited = set()
    current = head
    while current:
        if current in visited:
            return True  # Cycle detected!
        visited.add(current)
        current = current.next
    return False  # Reached None — no cycle

This works, but uses O(n) extra space. We can do better.

Floyd’s Cycle Detection Algorithm

Floyd’s algorithm uses two pointers moving at different speeds:

• Slow pointer (tortoise): moves 1 step at a time
• Fast pointer (hare): moves 2 steps at a time

Key insight: If there is a cycle, the fast pointer will eventually “lap” the slow pointer and they will meet inside the cycle. If there is no cycle, the fast pointer reaches None first.

Why they must meet

Think of two runners on a circular track. The faster runner gains one position on the slower runner every step. So the gap between them decreases by 1 each iteration. Eventually the gap becomes 0 — they meet.

Implementation

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


def has_cycle(head):
    """
    Floyd's cycle detection.
    Time: O(n), Space: O(1)
    """
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next        # 1 step
        fast = fast.next.next   # 2 steps

        if slow is fast:
            return True  # They met — cycle exists

    return False  # Fast reached end — no cycle

Tracing through an example

Consider: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (node 5 points back to node 3):

Step	Slow	Fast	Meet?
0	1	1	Start
1	2	3	No
2	3	5	No
3	4	4	YES

After just 3 steps, both pointers are at node 4 — cycle detected.

Finding the Cycle Start

Once we know a cycle exists, we often need to find where the cycle begins (the entry point). Floyd’s algorithm has a beautiful second phase for this.

The algorithm

1. After slow and fast meet inside the cycle, reset one pointer to the head.
2. Move both pointers one step at a time.
3. The point where they meet again is the cycle start.

def find_cycle_start(head):
    """
    Find the node where the cycle begins.
    Returns None if no cycle.
    Time: O(n), Space: O(1)
    """
    slow = head
    fast = head

    # Phase 1: Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # No cycle

    # Phase 2: Find entry point
    # Reset one pointer to head
    entry = head
    while entry is not slow:
        entry = entry.next
        slow = slow.next

    return entry  # This is the cycle start

Why does Phase 2 work?

Let’s define some variables:

• F = distance from head to cycle start
• C = cycle length
• a = distance from cycle start to meeting point

When slow and fast meet:

• Slow has traveled: F + a steps
• Fast has traveled: F + a + k*C steps (for some integer k, since fast looped around)
• Fast travels twice as far as slow: 2(F + a) = F + a + k*C
• Simplifying: F + a = k*C, or F = k*C - a

This means: the distance from head to cycle start (F) equals the distance from the meeting point to the cycle start going forward (k*C - a). So if you start one pointer at the head and one at the meeting point, both moving at speed 1, they meet at the cycle start.

# Verify with a concrete example
# List: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (cycle at node 3)
# F = 2 (head to node 3)
# C = 3 (cycle: 3 -> 4 -> 5 -> 3)
# Meeting point: node 4, so a = 1
# F = k*C - a = 1*3 - 1 = 2 ✓

Finding the Cycle Length

Once you find a point inside the cycle, walk around it counting steps until you return:

def cycle_length(head):
    """
    Find the length of the cycle (0 if no cycle).
    Time: O(n), Space: O(1)
    """
    slow = head
    fast = head

    # Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # Count the cycle
            count = 1
            current = slow.next
            while current is not slow:
                count += 1
                current = current.next
            return count

    return 0  # No cycle

Complete Solution: All Three Tasks

Here is a unified function that detects the cycle, finds its start, and measures its length:

def analyze_cycle(head):
    """
    Full cycle analysis.
    Returns (has_cycle, cycle_start_node, cycle_length)
    Time: O(n), Space: O(1)
    """
    slow = head
    fast = head

    # Phase 1: Detection
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return (False, None, 0)

    # Phase 2: Find start
    entry = head
    while entry is not slow:
        entry = entry.next
        slow = slow.next

    # Phase 3: Measure length
    length = 1
    current = entry.next
    while current is not entry:
        length += 1
        current = current.next

    return (True, entry, length)


# ---- Build a test list with a cycle ----
def build_cycle_list():
    nodes = [ListNode(i) for i in range(1, 7)]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    nodes[-1].next = nodes[2]  # 6 -> 3 (cycle start at node 3)
    return nodes[0]


head = build_cycle_list()
has_cycle, start, length = analyze_cycle(head)
print(f"Cycle: {has_cycle}")       # True
print(f"Start: {start.val}")       # 3
print(f"Length: {length}")          # 4 (3->4->5->6->3)

Edge Cases

Always handle these in interviews:

def has_cycle_safe(head):
    """Handle edge cases explicitly."""
    # Empty list
    if not head:
        return False

    # Single node pointing to itself
    if head.next is head:
        return True

    # Single node with no cycle
    if 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

Removing a Cycle

Once you find the cycle start, you can break it:

def remove_cycle(head):
    """
    Detect and remove a cycle from the linked list.
    Time: O(n), Space: O(1)
    """
    slow = head
    fast = head

    # Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return  # No cycle

    # Find the start of the cycle
    entry = head
    while entry is not slow:
        entry = entry.next
        slow = slow.next

    # Find the last node in the cycle (the one pointing to entry)
    last = entry
    while last.next is not entry:
        last = last.next

    # Break the cycle
    last.next = None

Complexity Analysis

Operation	Time	Space
Hash set detection	O(n)	O(n)
Floyd’s detection	O(n)	O(1)
Find cycle start	O(n)	O(1)
Find cycle length	O(n)	O(1)
Remove cycle	O(n)	O(1)

Why is Floyd’s O(n)? The fast pointer covers at most 2n nodes before either reaching None or meeting slow. After they meet, Phase 2 covers at most n nodes.

Related Techniques

Floyd’s algorithm is part of a broader family of fast/slow pointer techniques:

• Finding the middle of a list: When fast reaches the end, slow is at the middle
• Detecting palindromes: Reverse the second half after finding the middle
• Happy number detection: Same tortoise-and-hare on number transformations

def find_middle(head):
    """Find middle node using slow/fast. O(n) time, O(1) space."""
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # Middle node

Practice Problems

1. LeetCode 141 — Linked List Cycle: Basic cycle detection (Easy)
2. LeetCode 142 — Linked List Cycle II: Find cycle start (Medium)
3. LeetCode 287 — Find the Duplicate Number: Floyd’s on an array treated as a linked list (Medium)
4. LeetCode 202 — Happy Number: Floyd’s on number transformation (Easy)
5. LeetCode 876 — Middle of the Linked List: Slow/fast pointer for middle (Easy)

Key Takeaways

• Floyd’s algorithm detects cycles in O(n) time with O(1) space — no hash set needed.
• The mathematical proof relies on the fact that F = kC - a, which guarantees the two pointers meet at the cycle start in Phase 2.
• The same slow/fast pointer pattern applies to finding middles, detecting palindromes, and the duplicate number problem.
• Always handle edge cases: empty list, single node, single node pointing to itself.