How Do You Detect a Cycle in a Linked List?
Learn how to detect a cycle in a linked list using two pointers, with time complexity, code, and how to answer this interview question.
Expected Interview Answer
You detect a cycle in a linked list by walking it with two pointers moving at different speeds — a slow pointer advancing one node at a time and a fast pointer advancing two nodes at a time — and concluding a cycle exists if the fast pointer ever catches up to and equals the slow pointer, all in O(n) time and O(1) space.
If the list has no cycle, the fast pointer simply reaches null first and the walk ends cleanly with no match. If a cycle exists, both pointers eventually enter the loop, and because the fast pointer gains one extra step on the slow pointer every iteration, the gap between them shrinks by one each time until they land on the same node. An alternative is a hash set that records every visited node reference and reports a cycle the moment a node is seen twice, which is O(n) time but O(n) space, making the two-pointer approach strictly better for this specific question. This technique is commonly called Floyd’s cycle detection or the tortoise-and-hare algorithm.
- O(1) extra space, no auxiliary set needed
- O(n) time, single pass through the list
- Works without modifying node structure
- Extends naturally to finding the cycle’s start node
AI Mentor Explanation
Two fielders jog laps around the boundary rope to check if it forms a closed loop or a straight line to the pavilion gate. One fielder jogs at normal pace while the other jogs at double speed, both starting from the same spot. If the rope is a straight line, the faster fielder simply reaches the far gate and stops, proving there is no loop. If the rope loops back on itself, the faster fielder eventually laps the slower one and they meet on the rope, proving a closed loop exists.
Step-by-Step Explanation
Step 1
Initialize two pointers
Set slow = head and fast = head before starting the walk.
Step 2
Advance at different speeds
Each iteration, move slow one node forward and fast two nodes forward.
Step 3
Check for null or a match
If fast or fast.next becomes null, there is no cycle; if slow equals fast, a cycle exists.
Step 4
Optionally locate the cycle start
Reset one pointer to head and advance both one step at a time; they meet at the cycle’s entry node.
What Interviewer Expects
- Name the technique as Floyd’s cycle detection / tortoise and hare
- Correctly state O(n) time and O(1) space
- Explain why the fast pointer must eventually meet the slow pointer inside a cycle
- Mention the hash-set alternative and its O(n) space tradeoff
Common Mistakes
- Forgetting to check fast.next for null before dereferencing fast.next.next
- Starting fast and slow at different nodes instead of both at head
- Assuming a cycle can be detected by counting nodes without pointer comparison
- Confusing cycle detection with finding the cycle’s starting node (a separate follow-up step)
Best Answer (HR Friendly)
“I use two pointers walking the list at different speeds, one moving one step at a time and the other moving two steps at a time. If there is a loop, the faster pointer eventually catches up to the slower one and they land on the same node, which tells me a cycle exists without needing any extra memory.”
Code Example
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
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 FalseFollow-up Questions
- How would you find the exact node where the cycle begins?
- How would you determine the length of the cycle once detected?
- Why does the two-pointer approach use O(1) space compared to a hash-set approach?
- How would this approach change for a doubly linked list?
MCQ Practice
1. What is the space complexity of Floyd’s cycle detection algorithm?
It uses only two pointers regardless of list size, giving constant O(1) extra space.
2. In the two-pointer cycle check, how fast does the fast pointer move relative to the slow pointer?
The fast pointer advances two nodes per step while the slow pointer advances one, closing the gap by one node per iteration inside a cycle.
3. What does it mean if the fast pointer reaches null during the traversal?
Reaching null means the list terminates normally, so no cycle exists.
Flash Cards
What is another name for this cycle-detection technique? — Floyd’s cycle detection algorithm, or the tortoise-and-hare algorithm.
What is the time complexity of detecting a cycle with two pointers? — O(n), a single pass through the list.
What condition signals a cycle exists? — The slow and fast pointers reference the exact same node.
What is the space-complexity tradeoff of the hash-set alternative? — It uses O(n) space to store visited nodes, versus O(1) for the two-pointer method.