Linked List Cycle Detection With Floyd's Tortoise and Hare

This one is a Easy-rated classic reported from Amazon, Microsoft, Bloomberg interviews: "Linked List Cycle". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Fast and Slow Pointers pattern on sight. Part 1 of 11 in the Fast and Slow Pointers arc.

The Problem

Given the head of a linked list, determine if the list contains a cycle — that is, whether some node is reachable again by following next pointers. The constraint that makes it interesting: O(1) memory, ruling out the visited-set answer.

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

Recognizing the Fast and Slow Pointers Pattern

Fast and slow pointers (Floyd's tortoise and hare) walk the same structure at different speeds. If there is a cycle they must meet; if there is not, the fast pointer finds the end in half the iterations — which also locates midpoints without knowing the length. It is the default tool for linked lists and for any sequence defined by repeatedly applying a function, all in O(1) space.

Cycle detection in O(1) space is this pattern — it is the founding problem. A hash set of visited nodes works in O(n) space; the interviewer's follow-up is always the constant-space version, so start there.

The Approach

Slow moves one step, fast moves two. If the list ends, no cycle. If both are inside a cycle, the gap between them shrinks by exactly one node per iteration — fast gains one step on slow each round — so they must meet within one lap.

That gap argument is the piece to say out loud; the code is four lines and proves nothing by itself.

Python Solution

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


def has_cycle(head: ListNode | None) -> bool:
    """True if the linked list contains a cycle. O(1) space."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Complexity

• Time: O(n) — fast reaches the end or laps slow within a bounded number of steps
• Space: O(1) — two pointers, no visited set

Interview Tips and Follow-Ups

• Compare with is, not == — node identity, not value equality. Values can repeat.
• The guard order fast and fast.next handles both even and odd length lists; be able to explain why both checks are needed.
• Immediate escalation: return the node where the cycle begins — that is Linked List Cycle II, next in this arc.

If this clicked, continue the Fast and Slow Pointers arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.