Detect a Cycle in a Linked List: Floyd Algorithm and Cycle Entry

Detect a Cycle in a Linked List: Floyd’s Algorithm and Cycle Entry Point

Detecting a cycle in a linked list (LeetCode #141 and #142) is a foundational coding interview question. The base problem is “is there a cycle?”; the more interesting follow-up is “if so, find where the cycle begins.” Both are standard at FAANG, AI labs, and the broader tech interview circuit. The expected answer is Floyd’s tortoise-and-hare algorithm — fast and slow pointers — which solves both versions in O(n) time and O(1) space. This guide covers the mechanics, the math behind the cycle-entry trick, and the variations interviewers ask as follow-ups.

Problem Statement

Part 1: Given the head of a linked list, return True if there is a cycle (some node’s next points back to a previously-visited node), otherwise False.

Part 2: If a cycle exists, return the node where the cycle begins.

Approach 1: Hash Set (O(n) Space)

Walk the list. Track visited nodes in a hash set. If you encounter a node already in the set, that’s the cycle entry. If you reach None, no cycle.

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


def has_cycle_set(head: ListNode) -> bool:
    """O(n) time, O(n) space."""
    seen = set()
    while head:
        if head in seen:
            return True
        seen.add(head)
        head = head.next
    return False


def cycle_entry_set(head: ListNode) -> ListNode:
    """O(n) time, O(n) space."""
    seen = set()
    while head:
        if head in seen:
            return head
        seen.add(head)
        head = head.next
    return None

Complexity: O(n) time, O(n) space. Acceptable but suboptimal — interviewers will push for O(1) space.

Approach 2: Floyd’s Tortoise and Hare (O(1) Space)

Two pointers: one moves one step at a time (slow), the other moves two steps at a time (fast). If there’s a cycle, the fast pointer eventually laps the slow pointer and they meet inside the cycle. If there’s no cycle, the fast pointer reaches the end.

def has_cycle(head: ListNode) -> bool:
    """O(n) time, O(1) space — Floyd's tortoise and hare."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Complexity: O(n) time, O(1) space.

This is the answer the interviewer expects.

Finding the Cycle Entry Point

Once slow and fast meet inside the cycle, restart one pointer at the head and advance both at the same speed. They meet at the cycle entry.

def cycle_entry(head: ListNode) -> ListNode:
    """Return the node where the cycle begins, or None if no cycle."""
    if not head or not head.next:
        return None

    # Phase 1: detect cycle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # no cycle

    if slow != fast:
        return None  # no cycle (fast hit end)

    # Phase 2: find entry
    pointer = head
    while pointer != slow:
        pointer = pointer.next
        slow = slow.next
    return pointer

The Math Behind Phase 2

Why does restarting from the head and advancing at equal speed land exactly at the cycle entry? Let:

• L = distance from head to cycle entry
• C = length of the cycle
• x = distance from cycle entry to the meeting point (going around the cycle)

When slow and fast meet, slow has traveled L + x, fast has traveled L + x + kC for some integer k (fast made k extra laps). Fast moves twice as fast, so:

2(L + x) = L + x + kC ⇒ L + x = kC ⇒ L = kC - x

This means the distance from the head to the cycle entry equals (k laps minus x). If we restart one pointer at the head and advance both pointers one step at a time, after L steps the head pointer is at the entry, and the slow pointer has moved L additional steps from the meeting point — which lands it at the entry too (because x + L = kC, an integer number of laps). They meet at the cycle entry.

Strong candidates can sketch this argument verbally; full derivation isn’t usually expected in an interview but signals depth.

Common Variations

Cycle length

Once slow and fast meet, freeze slow and advance fast around the cycle. Count steps until fast meets slow again. That count is the cycle length.

def cycle_length(head: ListNode) -> int:
    """Return cycle length, or 0 if no cycle."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return 0

    if slow != fast:
        return 0

    length = 1
    fast = fast.next
    while fast != slow:
        fast = fast.next
        length += 1
    return length

Find duplicate number using cycle detection

(LeetCode #287) Given an array nums of n+1 integers in range [1, n], find the duplicate. Treat the array as a linked list where index i “points to” nums[i]. The duplicate causes a cycle, and the cycle entry is the duplicate value. Floyd’s algorithm finds it in O(n) time, O(1) space without modifying the array.

def find_duplicate(nums: list[int]) -> int:
    """Find duplicate in [1, n] in O(n) time, O(1) space."""
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    pointer = nums[0]
    while pointer != slow:
        pointer = nums[pointer]
        slow = nums[slow]
    return pointer

Happy number

(LeetCode #202) Compute the sum of squares of digits repeatedly. The sequence either reaches 1 (happy) or enters a cycle (not happy). Floyd’s algorithm detects the cycle in constant space.

Detecting cycles in directed graphs

Different problem: graph cycle detection uses DFS with three colors (white/gray/black) to detect back-edges. Floyd’s algorithm doesn’t directly apply because graph nodes have multiple successors.

Common Mistakes

• Off-by-one in fast pointer advancement. The check should be while fast and fast.next, not while fast.next (which crashes if fast is None). Both must be non-None for fast.next.next to be valid.
• Initializing slow and fast to head.next. Some implementations start them offset; this works for cycle detection but breaks the cycle-entry math. Use slow = fast = head.
• Forgetting the edge case of a single-node cycle. A node whose next points to itself: slow and fast meet immediately at the node. The cycle-entry phase should still work (head and slow are equal at start, and Phase 2 returns immediately).
• Using id() instead of object identity. Python’s default == on objects checks identity, which is correct here. Don’t override __eq__ on ListNode; if you do, comparison may compare values rather than nodes, breaking the algorithm.
• Modifying the list during traversal. Some bad solutions break the cycle by setting node.next = None, which destroys the input. Don’t mutate the list unless the problem allows it.

Frequently Asked Questions

See also: Check if a Linked List is a Palindrome • Reverse a Doubly Linked List • Serialize and Deserialize a Binary Tree

function hasCycle(head) {
    if (!head || !head.next) return false;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;          // Move 1 step
        fast = fast.next.next;     // Move 2 steps

        if (slow === fast) {
            return true;  // Cycle detected!
        }
    }

    return false;  // Fast reached end, no cycle
}

// Test with cycle
let node1 = { val: 1, next: null };
let node2 = { val: 2, next: null };
let node3 = { val: 3, next: null };
let node4 = { val: 4, next: null };

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2;  // Creates cycle

console.log(hasCycle(node1));  // true

// Test without cycle
let listNoCycle = { val: 1, next: { val: 2, next: null } };
console.log(hasCycle(listNoCycle));  // false

function detectCycle(head) {
    if (!head || !head.next) return null;

    let slow = head;
    let fast = head;

    // Phase 1: Detect if cycle exists
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            // Cycle detected!
            // Phase 2: Find start of cycle
            slow = head;

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

            return slow;  // This is the cycle start
        }
    }

    return null;  // No cycle
}