Linked List Cycle: Floyd's Tortoise and Hare
The Prompt
Given `head`, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer.
Understanding the Problem
If some node’s next pointer loops back to an earlier node, a plain traversal never terminates — you revisit the same nodes forever without any signal that you have looped. A hash set of visited nodes detects the repeat, but costs O(n) extra space.
Floyd’s tortoise-and-hare gets the same answer in O(1) space: run a slow pointer (one step per tick) and a fast pointer (two steps per tick). If the list ends, fast hits null and there is no cycle. If there is a cycle, both pointers eventually get trapped in it — and a faster runner on a circular track must lap a slower one.
The Interview Flow
Interviewer
How can you detect if a linked list has a cycle?
Candidate
A hash set could work. I could traverse the list and add each node to a set. If I encounter a node that's already in the set, there's a cycle. But this uses O(n) space.
Interviewer
That's correct. Is there a solution with O(1) space?
Candidate
Yes, the classic Floyd's Tortoise and Hare algorithm. I use two pointers, a "slow" pointer and a "fast" pointer.
Interviewer
How do they move?
Candidate
The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is no cycle, the fast pointer will reach the end of the list (null) first. If there is a cycle, the fast pointer will eventually "lap" the slow pointer, and they will meet at the same node.
Interviewer
Why is that guaranteed to happen?
Candidate
Once both pointers are in the cycle, the distance between them decreases by one at each step. Eventually, the distance will become zero, and they will meet. It's a bit like two runners on a circular track at different speeds.
Interviewer
Perfect. That's the optimal solution. Please implement it.
Why must the fast pointer catch the slow one?
The invariant once both pointers are inside the cycle: the gap from fast to slow (measured around the loop) shrinks by exactly one node per tick, because fast gains 2 − 1 = 1 step each round. A gap that decreases by 1 each tick cannot skip over 0 — it must reach 0, which is the moment they stand on the same node.
That meeting happens within one lap, so the whole check is O(n) time with two pointers of space. The trade-off versus the hash set is pure win here: same linear time, O(1) instead of O(n) memory — which is exactly why interviewers push past the set solution.
O(1) Space with Two Pointers (Tortoise and Hare)
- Handle the edge case: if `head` is null, there can be no cycle, so return `false`.
- Initialize a `slow` pointer and a `fast` pointer, both starting at `head`.
- Start a loop that continues as long as `fast` and `fast.next` are not null (to prevent errors when moving fast two steps).
- Inside the loop, advance `slow` by one step: `slow = slow.next`.
- Advance `fast` by two steps: `fast = fast.next.next`.
- Check if `slow` and `fast` are pointing to the same node. If `slow === fast`, a cycle is detected, so return `true`.
- If the loop completes, it means `fast` reached the end of the list, so there is no cycle. Return `false`.
Try it yourself
Write your solution and run it against 3 test cases.
Second value in each input is the index the tail links back to (-1 = no cycle).
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true;
}
}
return false;
}Explanation
Run slow and fast on 3 → 2 → 0 → -4, where -4 loops back to 2.
1Both pointers start at the head. Node -4 points back to node 2, so a naive walk would circle 2 → 0 → -4 forever.
2Tick 1: slow moves one step to 2; fast moves two steps to 0. Fast never hit null, so keep going.
3Tick 2: slow reaches 0; fast goes -4 → 2 (around the loop). Both are now inside the cycle, and the gap shrinks by one each tick.
4Tick 3: slow steps to -4; fast goes 0 → -4 and lands on the same node. They meet — return true, a cycle exists.
Complexity Analysis
TIME
O(n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.