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.
- The fast and slow pointer method, or Floyd's algorithm, detects a cycle in O(n) time and O(1) space.
- One pointer moves one step and another moves two steps, and they meet only if a cycle exists.
- A hash set of visited nodes also works but uses O(n) extra space, so it is the weaker answer.
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.
bool hasCycle(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}boolean hasCycle(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
return true;
}
return false;
}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.
Frequently asked questions
Why does the fast pointer move two steps?
Moving at different speeds guarantees the faster pointer laps the slower one inside any loop, so they eventually meet if a cycle is present.
How do you find the start of the cycle?
After the pointers meet, move one pointer back to the head and advance both one step at a time. They meet again at the cycle start.
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