#141 Linked List Cycle
Given the head of a linked list, decide whether the list contains a cycle.
That is, whether following next pointers ever revisits a node instead of
reaching null. Return true if a cycle exists, false otherwise.
Do it without modifying the list, and aim for O(1) extra memory, that constraint is the entire point of the problem.
Examples
Input
head = 3 → 2 → 0 → -4, with -4.next pointing back to the node 2Output
trueWalking the list gives 3, 2, 0, -4, 2, 0, -4, ... It never reaches null.
Input
head = 1 → 2, with 2.next pointing back to 1Output
trueA two-node loop is still a loop.
Input
head = 1Output
falseOne node whose next is null. The walk terminates.
Constraints
0 ≤ number of nodes ≤ 10⁴-10⁵ ≤ Node.val ≤ 10⁵A cycle, if present, is formed by the tail's next pointing at some earlier node
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.