LeetCode 141 · Linked List · concept: fast-slow-pointers

Problem

Return true if a linked list contains a cycle.

Approach 1 — hash set of visited nodes

Walk the list, storing each node; if you revisit one, there’s a cycle. O(n) time, O(n) space.

Approach 2 — Floyd’s tortoise and hare (optimal)

Two pointers, slow (1 step) and fast (2 steps). If there’s a cycle, fast laps slow and they meet; if fast reaches null, the list ends and there’s no cycle.

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Time O(n), space O(1).

Why they must meet inside a cycle

Once both pointers are in the loop, each step closes the gap between them by exactly one (fast gains 1 per tick). A gap that shrinks by 1 each step, in a finite cycle, reaches 0 — they can’t jump past each other. So a cycle guarantees a meeting; no cycle means fast hits null first.

Finding the cycle’s start (follow-up)

After they meet, move one pointer back to the head and advance both one step at a time; they meet again at the cycle’s entrance (a distance argument on loop length). This is the exact trick behind Find the Duplicate Number.

Key insight

Cycle detection in O(1) space → Floyd’s fast/slow pointers. Different speeds guarantee a collision inside any loop. This generalizes to any “sequence that eventually repeats” — including numeric sequences (Happy Number) and array-as-function problems.

↑ Back to NeetCode 150 — Solved