Linked List Cycle — Floyd's Tortoise and Hare Explained Step by Step

Problem Statement#

Given the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if there is some node in the list that can be reached again by continuously following the next pointer. Return true if there is a cycle, otherwise return false.

Constraints:

• The number of nodes in the list is in the range [0, 10^4]
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked list (used internally — you are not given pos)

Example 1:

Input:  head = [3, 2, 0, -4], pos = 1
Output: true
Explanation: Node at index 1 (value 2) is the tail's connection — a cycle exists.

Example 2:

Input:  head = [1, 2], pos = 0
Output: true

Example 3:

Input:  head = [1], pos = -1
Output: false
Explanation: No cycle.

Why This Problem Matters#

Linked List Cycle (LeetCode 141) is the canonical introduction to the fast/slow pointer (two-pointer) pattern on linked lists. Amazon, Microsoft, and Google ask this problem — or problems that use its detection as a sub-routine — with remarkable frequency. It appears in every major interview prep list because it sits at the intersection of pointer arithmetic, memory model understanding, and mathematical elegance.

The naive solution — use a hash set to remember visited nodes — works and runs in O(n) time, but it requires O(n) extra space. Interviewers immediately follow up with: "Can you do it in O(1) space?" That follow-up is the real test. If you know Floyd's algorithm, you look like a prepared engineer. If you reach for the hash set, you pass the problem but fail the follow-up.

Beyond the interview context, cycle detection is fundamental to operating system design (detecting deadlocks in resource graphs), compiler design (detecting circular imports), and database transaction management. Understanding why the tortoise and hare algorithm works prepares you for a whole class of mathematical reasoning in CS interviews.

The problem also acts as a gateway. Once you understand how slow and fast pointers interact, you can solve Linked List Cycle II (find the start of the cycle), Find the Duplicate Number (apply Floyd's on an array), and Happy Number — all using the same mental model.

The Core Insight#

Two runners on a circular track will always meet. If you put a slow runner (one step at a time) and a fast runner (two steps at a time) on a track with a loop, the fast runner will eventually lap the slow runner and they will occupy the same position. If there is no loop — a straight track — the fast runner reaches the end (null) and no meeting ever happens.

This is the entirety of Floyd's cycle detection algorithm: the fast pointer moves at 2x speed. If they meet, there is a cycle. If the fast pointer hits null, there is no cycle.

The O(1) space is the payoff — you need only two pointer variables regardless of how long the list is.

Visual Dry Run#

Input: 3 -> 2 -> 0 -> -4 -> (back to node 2)

At step 6, slow == fast — cycle detected, return true.

No-cycle trace: 1 -> 2 -> 3 -> None

fast is None — no cycle, return false.

Solution (Optimal)#

Python#

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next        # tortoise: one step
        fast = fast.next.next  # hare: two steps
        if slow is fast:
            return True         # they met — cycle exists
    return False                # fast hit None — no cycle

Time complexity: O(n) — in the worst case slow travels n steps before meeting fast or fast reaches null.

Space complexity: O(1) — only two pointer variables.

JavaScript#

var hasCycle = function(head) {
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;         // one step
        fast = fast.next.next;    // two steps
        if (slow === fast) return true;
    }
    return false;
};

Complexity:

Hash set alternative (simpler, but O(n) space):

def hasCycle(head):
    seen = set()
    while head:
        if id(head) in seen:
            return True
        seen.add(id(head))
        head = head.next
    return False

Common Mistakes#

1. Using == instead of is in Python for node comparison. In Python, == compares values, not identity. Two different nodes can have the same value. Always use is to compare node references (pointer equality), not ==.

2. Checking fast.next but not fast itself. The while condition must be while fast and fast.next. If fast is None, accessing fast.next will throw a NullPointerException or AttributeError. Always check fast is non-null first.

3. Moving slow and fast before the comparison. Always move both pointers first, then compare. If you compare before moving from the initial state, they both start at head and you'd incorrectly return true on the first iteration.

4. Off-by-one in the fast step. fast = fast.next.next — two steps. Not fast.next.next.next. The hare moves exactly twice as fast as the tortoise.

5. Forgetting the edge case of an empty list. If head is None, fast starts as None and the while condition is immediately false — return false. This is handled automatically if you initialize correctly, but it's worth verifying your code handles the empty list without crashing.

Interview Tips#

When you see this problem in an interview, do the following:

1. Clarify — Ask: "Should I return true/false, or the actual cycle node?" (This problem is just true/false, but Cycle II asks for the node.)

2. Mention the naive solution first — "A hash set works in O(n) time and O(n) space. But I'll use Floyd's algorithm for O(1) space."

3. Explain the intuition verbally — "Two runners on a loop always meet. One moves one step, the other two steps. If there's a cycle, they collide. If not, the faster one exits."

4. Trace through the example on the whiteboard or scratch paper before coding.

5. Follow-up ready — Know that if the interviewer asks "find where the cycle starts," that's LeetCode 142, solved by resetting one pointer to head after the meeting point.

Follow-up Questions#

Q: Can you find where the cycle starts (not just detect it)? Yes — that's LeetCode 142 (Linked List Cycle II). After slow and fast meet, reset one pointer to head. Move both one step at a time. They meet again at the cycle entry point due to a mathematical property of Floyd's algorithm.

Q: What if the list can have multiple cycles? A standard singly-linked list can only have one cycle (since each node has one next pointer). The question is only about detecting if any cycle exists.

Q: Can you use recursion? Recursion is not naturally suited here because you need to track two pointers moving at different speeds across the list. The iterative two-pointer approach is both simpler and more efficient.

Q: What is the time complexity when a cycle exists? When a cycle of length c exists and the pre-cycle portion has length d, the slow pointer needs at most d + c steps before meeting the fast pointer. So it is still O(n).

Q: How does this apply to the "Happy Number" problem? In the Happy Number problem, the sequence of sum-of-squares operations either terminates at 1 or enters a cycle. You can apply the exact same slow/fast pointer idea to detect the cycle without a hash set.

Key Takeaways#

• Floyd's tortoise and hare algorithm detects cycles in O(n) time with O(1) space — no hash set needed.
• The key guard condition is while fast and fast.next to prevent null pointer errors.
• In Python, use is (not ==) for pointer/node identity comparison.
• This pattern directly extends to: find cycle start (LC 142), find duplicate number (LC 287), and happy number (LC 202).
• If an interviewer asks a follow-up about O(1) space, Floyd's is the answer — always be ready to pivot to it.
• The algorithm works because on a circular track, the faster runner will always lap and meet the slower runner.