How do you detect a cycle in a linked list?

Short answer: Floyd’s tortoise and hare: slow moves 1, fast moves 2. If they meet, there is a cycle. To find the cycle entrance, reset one pointer to head and move both one step until they meet.

Complexity

Time O(n), Space O(1) — better than HashSet of visited nodes.

Common follow-ups

• Find cycle start
• Find cycle length

Mention both HashSet and Floyd; then choose Floyd for O(1) space.