Skip to main content

9. Linked List Cycle

easyAsked at Snap

Determine whether a linked list has a cycle. Snap uses this to test pointer fluency and to see if you reach for Floyd's tortoise-and-hare instead of a hash set.

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

Source citations

Public interview reports confirming this problem appears in Snap loops.

  • Glassdoor (2026-Q1)— Snap onsite reports cite Floyd's algorithm as the expected solution.
  • Blind (2025-12)— Often followed by 'find the cycle start' (LC 142).

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
  • pos is -1 or a valid index in the linked list.

Examples

Example 1

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

Example 2

Input
head = [1,2], pos = 0
Output
true

Example 3

Input
head = [1], pos = -1
Output
false

Approaches

1. Hash set of visited nodes

Walk the list and store node references in a Set. Cycle detected when you see a duplicate reference.

Time
O(n)
Space
O(n)
function hasCycle(head) {
  const seen = new Set();
  while (head) {
    if (seen.has(head)) return true;
    seen.add(head);
    head = head.next;
  }
  return false;
}

Tradeoff: Correct but uses O(n) extra memory. Snap will push for O(1) auxiliary space.

2. Floyd's tortoise and hare (optimal)

Two pointers — slow moves one step, fast moves two. If they ever meet, there's a cycle. If fast reaches 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) space using the classic two-pointer trick. The two-pointer race is a fundamental low-latency pattern Snap values.

Snap-specific tips

At Snap, expect a follow-up to find the cycle's start (LC 142). Mention you know the math — once they meet, restart one pointer at head and advance both one step at a time. Snap engineers see this as the same pattern they use for detecting playback loops in their video pipeline.

Common mistakes

  • Checking fast.next.next without first ensuring fast and fast.next are non-null.
  • Starting fast at head.next instead of head — works but breaks the symmetry needed for the LC 142 follow-up.
  • Comparing values instead of references — value equality breaks on duplicates.

Follow-up questions

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

  • Find the node where the cycle begins (LC 142).
  • Find the length of the cycle.
  • Detect a cycle in an undirected graph (LC 261).

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 actually work?

Once both pointers enter the cycle, the fast pointer gains one step on the slow pointer per iteration. Eventually it catches up modulo cycle length, so they must collide within O(cycle length) steps.

Does this catch a one-node self-loop?

Yes. slow advances to head.next, fast advances to head.next.next which equals head (self-loop). After one more iteration they coincide.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →