How do you detect a cycle in a linked list?
The best way to detect a cycle in a linked list is the fast and slow pointer method, also called Floyd's cycle detection. You move one pointer one step at a time and another two steps at a time. If they ever meet, there is a cycle. If the fast pointer reaches the end, there is no cycle. It uses O(n) time and O(1) space.
Why two pointers work
Picture two runners on a circular track, one twice as fast as the other. On a loop the faster runner eventually laps and meets the slower one. On a straight track the faster runner just reaches the end and they never meet.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return FalseWhy not just use a set
You could store every node you visit in a hash set and check for repeats, which also works but uses O(n) extra space. The two pointer method is preferred because it uses only O(1) space.
Mention both approaches. Say the hash set method is simpler but uses O(n) space, while the fast and slow pointer method uses O(1) space, so it is the better answer. Offering the trade off shows range.
Common follow up questions
Related interview questions
Want the full DSA guide?
Read every DSA concept with notes, diagrams, and code in one place. Track your progress as you go.
Open the DSA guide All DSA questions