141. Linked List Cycle

Q: 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.

Q: 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.

easyAsked at Intel

Detect 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 Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

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

Input

head = [3,2,0,-4], pos = 1

Output

true

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2

Input

head = [1,2], pos = 0

Output

true

Example 3

Input

head = [1], pos = -1

Output

false

Explanation: 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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Linked List Cycle and other Intel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →