141. Linked List Cycle

Q: Why is Floyd's algorithm guaranteed to terminate?

If there's no cycle, fast will hit null because lists are finite. If there is a cycle, both pointers are eventually trapped inside it; fast gains one position per step on slow, and within a cycle of length C the relative position cycles modulo C — so they meet within C steps. The total time is bounded by n + C <= 2n = O(n).

Q: Can I use the hash-set approach in an IBM interview?

Yes, as a starting point — but always volunteer Floyd's as the O(1)-space follow-up before the interviewer asks. Public IBM reports consistently note that candidates who only ship the hash-set version get a 'meets bar' rating; those who derive Floyd's get 'strong yes.'

easyAsked at IBM

Linked List Cycle is IBM's Floyd's-tortoise-and-hare screener. The interviewer is grading whether you reach for the two-pointer technique unprompted, articulate why the fast pointer catches the slow one inside a cycle, and ship O(1) extra space.

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

Glassdoor (2026-Q1)— IBM SWE-1 and SWE-2 recurring linked-list question.
LeetCode (2026-Q1)— Top-30 IBM-tagged problem.
GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive (Floyd's algorithm coverage).

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

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. Hash set of visited nodes

Walk the list. Add each node reference to a Set; if you see a node you've already added, there's a cycle.

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

function hasCycleSet(head) {
  const seen = new Set();
  let curr = head;
  while (curr !== null) {
    if (seen.has(curr)) return true;
    seen.add(curr);
    curr = curr.next;
  }
  return false;
}

Tradeoff: Simple and ships in 6 lines. Fails the 'do it in O(1) extra space' follow-up — which the interviewer almost always asks. Always mention the two-pointer alternative.

2. Floyd's tortoise and hare (optimal)

Two pointers: slow steps by 1, fast steps by 2. If they ever meet, there's a cycle. If fast hits null, there isn't.

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

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Tradeoff: O(n) time, O(1) space — the canonical answer. The proof: inside a cycle, fast gains one position per step on slow, so they must meet within at most C steps where C is the cycle length. The trick is checking BOTH fast and fast.next for null to avoid dereferencing null in the next-next jump.

IBM-specific tips

IBM specifically tests the two-pointer technique on this problem because it has a clean O(1)-space optimal. The grader is watching for two things: (1) the null-safety on `fast` AND `fast.next` (forgetting one leads to a null deref on linear lists), (2) the proof that the pointers meet — saying 'fast gains 1 position per step inside a cycle so they meet in at most C iterations' demonstrates you understand WHY it works.

Common mistakes

Checking only `fast !== null` and not `fast.next !== null` — null deref on `fast.next.next` for any linear list.
Initializing slow = head.next and fast = head — works but introduces edge cases on single-node lists.
Returning true when slow === head — incorrect for a non-cyclic list (slow starts AT head).
Using `slow !== fast` as the loop condition instead of checking inside the loop — fails because they start equal.

Follow-up questions

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

Linked List Cycle II — return the node where the cycle begins (LeetCode 142).
Find Duplicate Number (LeetCode 287) — Floyd's applied to an array.
Detect a cycle in a directed graph.
Find the length of the cycle if one exists.

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 is Floyd's algorithm guaranteed to terminate?

If there's no cycle, fast will hit null because lists are finite. If there is a cycle, both pointers are eventually trapped inside it; fast gains one position per step on slow, and within a cycle of length C the relative position cycles modulo C — so they meet within C steps. The total time is bounded by n + C <= 2n = O(n).

Can I use the hash-set approach in an IBM interview?

Yes, as a starting point — but always volunteer Floyd's as the O(1)-space follow-up before the interviewer asks. Public IBM reports consistently note that candidates who only ship the hash-set version get a 'meets bar' rating; those who derive Floyd's get 'strong yes.'

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →