Linked list cycle

Given the head of a linked list, return whether some node can be reached again by following next pointers, that is, whether the list contains a cycle.

Before you code

A set of visited nodes works but uses O(n) memory. Aim for O(1): two pointers moving at different speeds.

Hints

1. Start slow and fast at the head. Each round, slow moves one node and fast moves two.
2. If fast or fast.next becomes null, the list ends: no cycle.
3. If slow and fast ever point to the same node, there is a cycle. Compare node identity, not values.
4. Follow-up (LeetCode "Linked list cycle II"): return the node where the cycle starts, by restarting one pointer at the head.

Production & complexity notes

When solving Linked list cycle on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Fast and slow pointers to reinforce the underlying pattern.

What it practices

Floyd's cycle detection and why the pointers must meet, from Fast and slow pointers.