141. Linked List Cycle
easyAsked at CiscoLinked List Cycle at Cisco is the second-most common pointer warm-up after Reverse Linked List. The interviewer wants Floyd's tortoise-and-hare so you can detect the loop in O(1) extra space. The hash-set version is the fallback when you can't articulate why two pointers eventually meet.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Cisco loops.
- Glassdoor (2026-Q1)— Cisco SDE-I phone screens report Linked List Cycle as a recurring warm-up.
- Levels.fyi (2025-12)— Cisco new-grad interview reports list this as a standard 10-minute round.
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: Tail node connects back to node at index 1.
Example 2
head = [1,2], pos = 0trueExample 3
head = [1], pos = -1falseApproaches
1. Hash set of visited nodes (brute force)
Walk the list and record every node reference. If you ever revisit, there's a cycle. If you hit null, there isn't.
- Time
- O(n)
- Space
- O(n)
function hasCycleBrute(head) {
const seen = new Set();
let cur = head;
while (cur) {
if (seen.has(cur)) return true;
seen.add(cur);
cur = cur.next;
}
return false;
}Tradeoff: Simple to reason about. Wrong space complexity for the rubric — Cisco wants O(1). Bring this up as the strawman before pivoting to Floyd's.
2. Floyd's tortoise and hare (optimal)
Two pointers: slow moves one step, fast moves two. If there's a cycle they meet inside it. If fast hits null, no cycle.
- Time
- O(n)
- Space
- O(1)
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;
}Tradeoff: O(1) extra space, single pass. The 'why does this work?' explanation: once both pointers are inside the cycle, fast gains one step per iteration on slow. In a cycle of length C, they meet in at most C iterations. That's the full intuition.
Cisco-specific tips
Cisco interviewers expect Floyd's by name. Say 'I'll use Floyd's tortoise-and-hare with two pointers' before writing code, then explain why fast catches slow inside the cycle. If you only know the hash-set version, write it but immediately follow with 'O(1) variant is Floyd's — slow + fast pointer, they meet inside a cycle.'
Common mistakes
- Forgetting to check `fast.next` before `fast.next.next` — null dereference when the list ends.
- Initializing fast to `head.next` instead of `head` — works but creates a subtle off-by-one in the LC 142 follow-up.
- Returning false too early — must wait for the loop to exit (fast hits null) before concluding no cycle.
Follow-up questions
An interviewer at Cisco may pivot to one of these next:
- Linked List Cycle II (LC 142) — return the NODE where the cycle starts. Floyd's again: after they meet, reset slow to head and step both one at a time.
- Happy Number (LC 202) — Floyd's on a sequence of digit-squared-sums (same algorithm, different graph).
- Find the Duplicate Number (LC 287) — Floyd's on an array treated as a linked list.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does Floyd's actually work?
Once both pointers enter the cycle of length C, fast gains 1 net step per iteration on slow. So after at most C iterations, fast = slow (mod C). The pre-cycle 'tail' doesn't matter because both pointers enter at the same time once slow walks the tail.
Is the hash-set version acceptable?
It correctly returns true/false, so yes on rubric. But Cisco interviewers specifically expect O(1) on this question because the canonical answer is Floyd's. Use the hash-set only if you can't recall the two-pointer trick — and follow up immediately with 'I know there's an O(1) variant called Floyd's.'
Free learning resources
Curated free links for this problem.