Skip to main content

19. Linked List Cycle

easyAsked at Snowflake

Determine whether a linked list has a cycle using O(1) space. Snowflake asks this because Floyd's tortoise-and-hare is a textbook example of how to convert from O(n) to O(1) auxiliary space — a recurring theme in their constant-memory streaming kernels.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake execution-engine team uses this in onsites.
  • LeetCode Discuss (2025-10)— Reported at Snowflake new-grad screens.

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

Approaches

1. Visited set

Walk the list; store visited nodes in a set; cycle iff we revisit.

Time
O(n)
Space
O(n)
function hasCycle(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: Linear time but O(n) space. Mention as the baseline.

2. Floyd's tortoise and hare (optimal)

Two pointers: slow advances one step, fast advances two. If there's a cycle, they meet. If fast hits null, there's no cycle.

Time
O(n)
Space
O(1)
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Tradeoff: O(1) space. The key insight: in a cycle, fast laps slow, and they must collide. This pattern generalizes to cycle entry detection.

Snowflake-specific tips

Snowflake interviewers grade this on whether you arrive at Floyd's algorithm without prompting and can explain why fast lapping slow guarantees a meeting. Bonus signal: discuss when this matters in their system — detecting cycles in computed-column dependency graphs or in CTE references during query compilation.

Common mistakes

  • Checking slow == fast before advancing — they always start equal at head.
  • Forgetting the fast && fast.next null check, causing a null-pointer dereference at the tail.
  • Confusing this with finding the cycle entry (LC 142) — that's the harder variant.

Follow-up questions

An interviewer at Snowflake may pivot to one of these next:

  • Find the start of the cycle (LC 142).
  • Length of the cycle.
  • How would you detect cycles in a SQL CTE reference graph?

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 does Floyd's guarantee a meeting in a cycle?

Inside the cycle, fast gains 1 step per iteration on slow. The gap is bounded by the cycle length, so within cycle-length steps they collide.

Why does Snowflake care?

When validating a recursive CTE or a view that references other views, the compiler must reject cycles. The graph traversal uses the same cycle-detection logic.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →