Detect Cycle in Linked List —
Tortoise and hare always meet.
Floyd's cycle detection algorithm uses two pointers — slow moves one step, fast moves two. If there's a cycle, fast will lap slow and they'll meet inside the loop. If there's no cycle, fast reaches None first. Watch the two pointers chase each other on LearnBug and the meeting inside the cycle becomes visually obvious.
What is Floyd's Cycle Detection?
Two pointers start at head. slow moves one node per step. fast moves two nodes per step. If a cycle exists, fast will eventually catch up to slow — they're both going around the same loop, and since fast closes the gap by one step per iteration, they must meet. If no cycle, fast hits None and we return False.
Why O(1) space — no visited set needed
The naive approach stores visited nodes in a hash set — O(n) space. Floyd's uses only two pointers — O(1). On LearnBug you see both pointers on the same node diagram, slow creeping forward while fast takes two steps at a time, until the inevitable collision inside the cycle.
List: 1 → 2 → 3 → 4 → 5 → (back to 3)
Nodes 3, 4, 5 form a cycle. Slow moves ×1, fast moves ×2.
slow = head (1), fast = head (1)
slow → 2 (×1). fast → 3 (×2).
Fast takes two steps: 1→2→3. Slow takes one: 1→2. No meeting yet.
slow → 3. fast → 5.
Slow: 2→3. Fast: 3→4→5. Fast is now 2 nodes ahead in the cycle section.
slow → 4. fast → 4 (5→3→4). They meet at node 4!
Fast: 5→(back to 3)→4. Slow: 3→4. Both at node 4 — cycle detected! Return True.
slow == fast → cycle detected ✓
When fast reaches None → no cycle
Linear list: fast.next or fast.next.next becomes None
In a list without a cycle, fast advances two steps and eventually runs off the end. When fast or fast.next is None, return False.
fast == None → no cycle ✓
Floyd's algorithm + hash set alternative
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # one step
fast = fast.next.next # two steps
if slow == fast:
return True # cycle detected
return False # fast hit None — no cycledef has_cycle_set(head):
visited = set()
curr = head
while curr:
if id(curr) in visited:
return True # revisited a node
visited.add(id(curr))
curr = curr.next
return FalseTime & Space Complexity
Frequently asked questions
Why must slow and fast always meet if a cycle exists?
Once both pointers are inside the cycle, think of fast as chasing slow from behind. Each iteration, fast closes the gap by exactly 1 (it moves 2, slow moves 1). The gap starts at some value d and decreases by 1 each step — it must eventually reach 0. So they always meet. The gap never skips over 0 because it decrements by exactly 1.
How do you find the start of the cycle, not just detect it?
After detecting the meeting point, reset slow to head and keep fast at the meeting point. Now advance both one step at a time. Where they meet again is the cycle entry node. This is proven mathematically by the distances involved in the cycle. LeetCode 142 — Linked List Cycle II.
What if the list has only one node?
If a single node points to itself, fast.next is the node itself and fast.next.next is also the node — the loop runs and slow == fast on the first iteration. If the single node points to None, fast.next is None — the while condition fails immediately and we return False correctly.
Why check fast and fast.next in the while condition?
We access fast.next.next inside the loop. If fast is None, fast.next throws AttributeError. If fast.next is None, fast.next.next throws AttributeError. The condition fast and fast.next guards against both — short-circuit evaluation prevents the inner access if either is None.
What are the LeetCode problems for this?
LC 141 — Linked List Cycle (detect: return bool). LC 142 — Linked List Cycle II (find the entry node). LC 287 — Find the Duplicate Number (array as implicit linked list with cycle). All three use Floyd's algorithm. Mastering LC 141 first makes 142 and 287 straightforward.
Watch slow and fast chase each other through the cycle
Paste your linked list into LearnBug and see both pointers converge step by step.