141. Linked List Cycle
easyAsked at IntelDetect whether a singly linked list contains a cycle. Intel reaches for Floyd's tortoise-and-hare because it's the textbook O(1)-space pointer trick; senior candidates also derive WHY two pointers at different speeds must meet inside a cycle (modular-arithmetic argument).
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Intel loops.
- Glassdoor (2026-Q1)— Intel SWE phone-screen reports cite cycle-detection as a recurring Floyd's-algorithm ask.
- GeeksforGeeks (2025-09)— Intel Interview Experience archives reference Floyd's tortoise-and-hare.
- LeetCode discuss (2025-11)— Intel-tagged in the LC company-frequency listing.
Problem
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. Return true if there is a cycle in the linked list. Otherwise, return false.
Constraints
The number of the nodes in the list is in the range [0, 10^4].-10^5 <= Node.val <= 10^5
Examples
Example 1
head = [3,2,0,-4], pos = 1trueExplanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2
head = [1,2], pos = 0trueExample 3
head = [1], pos = -1falseExplanation: There is no cycle in the linked list.
Approaches
1. Hash set (brute)
Walk the list, adding each node to a set. If you see a node you've already visited, there's a cycle.
- Time
- O(n)
- Space
- O(n)
function hasCycleHash(head) {
const seen = new Set();
let curr = head;
while (curr) {
if (seen.has(curr)) return true;
seen.add(curr);
curr = curr.next;
}
return false;
}Tradeoff: Easy to write, easy to reason about, but O(n) space. The two-pointer version achieves O(1) space — that's what Intel grades on.
2. Floyd's tortoise and hare (optimal)
Walk two pointers: slow advances 1, fast advances 2. If there's no cycle, fast hits null. If there is, fast eventually laps slow and they meet.
- Time
- O(n)
- Space
- O(1)
function hasCycle(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}Tradeoff: Linear time, constant space. The senior signal is articulating WHY they must meet: inside a cycle of length L, the gap between fast and slow decreases by 1 each step (since fast gains 1 on slow per step). After at most L steps, the gap is 0 — they meet.
Intel-specific tips
Intel will absolutely ask 'why does fast catch slow?' as the follow-up. The modular-arithmetic argument lands: once both pointers are inside the cycle (which takes at most n steps), they're moving around a loop of length L. The signed distance from slow to fast (mod L) decreases by exactly 1 each step. It hits 0 (collision) within L steps. Total work: O(n) until both enter cycle + O(L) for collision = O(n).
Common mistakes
- Forgetting the `fast.next !== null` check — accessing `.next.next` on a null next causes a crash for odd-length non-cyclic lists.
- Starting both pointers at different nodes — the standard is both at head; starting fast at head.next is also valid but the loop condition shifts.
- Conflating with Find the Duplicate Number (LC 287) — the cycle-detection idea is the same but you also need the cycle-entry point (Floyd's second phase).
Follow-up questions
An interviewer at Intel may pivot to one of these next:
- Linked List Cycle II (LC 142) — find the node where the cycle begins. (Hint: after they meet, restart one pointer from head and walk both at speed 1 — they meet at the cycle entry.)
- Find the Duplicate Number (LC 287) — treat indices as nodes and apply Floyd's.
- Happy Number (LC 202) — apply Floyd's to the digit-square iteration.
- What if you don't trust the hash set's collision behavior? (Use node-identity by reference; in C, by pointer.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why must fast catch slow inside a cycle?
Inside a cycle of length L, model positions modulo L. Fast - Slow (mod L) decreases by 1 each step (fast gains 1 per step, modular subtraction). After at most L steps, the difference hits 0 — collision.
Could fast skip over slow without meeting?
No — each step, fast gains exactly 1 on slow. The gap is a non-negative integer that decreases by 1 each step, so it must hit 0 (not skip past) before going negative. They land on the same node.
Free learning resources
Curated free links for this problem.