LeetCode 141 ·
Easy
Linked List Cycle
Return true if the linked list contains a cycle.
Try it
Step through the core mechanic. The simulator below runs the linked list shape this problem is built on.
Interactive · Floyd's tortoise & hare slow moves ×1, fast moves ×2; if they meet, there's a cycle
(use -1 for "no cycle")
both pointers at head
Why it works.
If a cycle exists, fast (moving ×2) and slow (moving ×1) close the gap on
each step by exactly 1. Inside the loop the gap shrinks by one each
iteration; meeting is inevitable in at most cycle-length steps.
The second phase (reset slow, advance both ×1) finds the entry by a
number-theory argument: distance from head to entry equals distance from
meet point to entry around the loop.
The approach
Floyd's tortoise and hare: a slow pointer moves one step, fast moves two. If they ever meet there is a cycle; if fast reaches null the list is acyclic.
| Aspect | Value |
|---|---|
| Pattern | Linked list |
| Recognise it by | Detect a loop with O(1) space. |
| Time complexity | O(n) |
| Space complexity | O(1) |
| Difficulty | Easy |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.