9. Linked List Cycle

Q: Why does Floyd's algorithm always terminate?

If no cycle, fast hits null and we return false. If cycle, slow enters the cycle and fast laps it in finite steps.

Q: Is fast === slow always true on the first overlap?

Yes — fast moves 1 step closer to slow each iteration inside the cycle, so they coincide before slow could escape.

easyAsked at Square

Detect whether a linked list contains a cycle. Square tests Floyd's tortoise-and-hare to gauge pointer dexterity and constant-space thinking — the same care needed when traversing offline transaction journals that may have malformed forward refs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Square loops.

Glassdoor (2025)— Square POS firmware screen.
LeetCode Discuss (2026-Q1)— Cash App backend SRE.

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 some node in the list 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: 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 and store node references in a Set. Cycle iff you revisit.

Time: O(n)
Space: O(n)

function hasCycle(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: O(n) space. Square explicitly probes for the O(1) follow-up.

2. Floyd's tortoise and hare

Walk slow by 1, fast by 2. If they meet, there's a cycle. If fast hits null, 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: Constant space. Fast always laps slow inside the cycle — formal proof relies on modular arithmetic of cycle length.

Square-specific tips

Square interviewers grade this on whether you immediately reach for the two-pointer technique and can explain WHY they meet (fast gains 1 step per iteration inside the cycle, so it will eventually align with slow modulo cycle length). Bonus signal: outline the LC-142 follow-up (find the cycle's entry point) before they ask.

Common mistakes

Iterating fast without checking fast.next exists — null deref.
Returning false on slow === fast at the start (both at head); use a do-while or skip the initial check.
Using Set of values instead of node references — values can repeat without a cycle.

Follow-up questions

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

Linked List Cycle II (LC 142): return the cycle's entry node.
Find the length of the cycle.
How would you adapt this to detect cycles in a transaction-event DAG?

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 algorithm always terminate?

If no cycle, fast hits null and we return false. If cycle, slow enters the cycle and fast laps it in finite steps.

Is fast === slow always true on the first overlap?

Yes — fast moves 1 step closer to slow each iteration inside the cycle, so they coincide before slow could escape.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →