141. Linked List Cycle
easyAsked at IBMLinked List Cycle is IBM's Floyd's-tortoise-and-hare screener. The interviewer is grading whether you reach for the two-pointer technique unprompted, articulate why the fast pointer catches the slow one inside a cycle, and ship O(1) extra space.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in IBM loops.
- Glassdoor (2026-Q1)— IBM SWE-1 and SWE-2 recurring linked-list question.
- LeetCode (2026-Q1)— Top-30 IBM-tagged problem.
- GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive (Floyd's algorithm coverage).
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^5pos is -1 or a valid index in the linked-list.
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 = -1falseApproaches
1. Hash set of visited nodes
Walk the list. Add each node reference to a Set; if you see a node you've already added, there's a cycle.
- Time
- O(n)
- Space
- O(n)
function hasCycleSet(head) {
const seen = new Set();
let curr = head;
while (curr !== null) {
if (seen.has(curr)) return true;
seen.add(curr);
curr = curr.next;
}
return false;
}Tradeoff: Simple and ships in 6 lines. Fails the 'do it in O(1) extra space' follow-up — which the interviewer almost always asks. Always mention the two-pointer alternative.
2. Floyd's tortoise and hare (optimal)
Two pointers: slow steps by 1, fast steps by 2. If they ever meet, there's a cycle. If fast hits null, there isn't.
- Time
- O(n)
- Space
- O(1)
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}Tradeoff: O(n) time, O(1) space — the canonical answer. The proof: inside a cycle, fast gains one position per step on slow, so they must meet within at most C steps where C is the cycle length. The trick is checking BOTH fast and fast.next for null to avoid dereferencing null in the next-next jump.
IBM-specific tips
IBM specifically tests the two-pointer technique on this problem because it has a clean O(1)-space optimal. The grader is watching for two things: (1) the null-safety on `fast` AND `fast.next` (forgetting one leads to a null deref on linear lists), (2) the proof that the pointers meet — saying 'fast gains 1 position per step inside a cycle so they meet in at most C iterations' demonstrates you understand WHY it works.
Common mistakes
- Checking only `fast !== null` and not `fast.next !== null` — null deref on `fast.next.next` for any linear list.
- Initializing slow = head.next and fast = head — works but introduces edge cases on single-node lists.
- Returning true when slow === head — incorrect for a non-cyclic list (slow starts AT head).
- Using `slow !== fast` as the loop condition instead of checking inside the loop — fails because they start equal.
Follow-up questions
An interviewer at IBM may pivot to one of these next:
- Linked List Cycle II — return the node where the cycle begins (LeetCode 142).
- Find Duplicate Number (LeetCode 287) — Floyd's applied to an array.
- Detect a cycle in a directed graph.
- Find the length of the cycle if one exists.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is Floyd's algorithm guaranteed to terminate?
If there's no cycle, fast will hit null because lists are finite. If there is a cycle, both pointers are eventually trapped inside it; fast gains one position per step on slow, and within a cycle of length C the relative position cycles modulo C — so they meet within C steps. The total time is bounded by n + C <= 2n = O(n).
Can I use the hash-set approach in an IBM interview?
Yes, as a starting point — but always volunteer Floyd's as the O(1)-space follow-up before the interviewer asks. Public IBM reports consistently note that candidates who only ship the hash-set version get a 'meets bar' rating; those who derive Floyd's get 'strong yes.'
Free learning resources
Curated free links for this problem.