Cycle Detection Interview Questions
How do you detect a cycle in a linked list? — spoken sample answer for Indian interviews.
- 5Questions with answers
- 3Difficulty levels
Questions (5)
Browse beginner, intermediate, and advanced questions with answers — hide them when you want to self-test.
How do you detect a cycle in a linked list?
Determine whether a linked list contains a cycle.
Store visited node identities in a hash set while walking the list. Complexity: Time O(n) , Space O(n)
Floyd's tortoise and hare — slow moves one step, fast moves two. If they meet, a cycle exists; if fast hits null, no cycle. Complexity: Time O(n) , Space O(1)
To find cycle start, reset one pointer to head and move both one step at a time — the meeting point is the entrance.
Single-node list, full loop back to head.
After detecting a cycle, how do you find the start of the cycle?
When slow and fast meet, I put one pointer back at the head. I move both one step at a time. Their next meeting is the entrance. The math is: they meet at a point k steps inside the loop, and the remaining loop length equals the distance from head to entrance. I would not count loop length first unless they ask. I would also handle no cycle — fast hits null — and a cycle at head, where the entrance is head itself.
How do you find the length of the cycle?
Once they meet, I freeze one pointer and walk the other around until it meets again, counting steps. That count is the loop length. Then I can still find the entrance with the head trick. I would not modify node values to mark them unless the interviewer allows mutating. Constant extra memory is the point of Floyd.
Why not always use a hash set of node identities?
A hash set is O(n) extra memory and easier to write. In production I might use it if n is small and I cannot risk pointer bugs. In interviews they almost always want O(1) extra space, which is Floyd. Hashing also fails if they ask me not to use extra structures. I would mention both, then implement Floyd unless they say otherwise.
How do you remove a cycle if you are allowed to mutate the list?
Find the start of the cycle, walk to the node whose next is the start, and set next to null. If the cycle includes head, the node before head in the loop is the tail. I would not break a random link inside the loop — that can drop nodes. Detect, find entrance, cut the predecessor. Then I can run a walk to null to prove it is a list again.
Practice with AI mock interviews
Run DSA mock interviews with AI follow-ups, instant feedback, and analytics on AiLx.
Free to start · No credit card required