Skip to main content

11. Linked List Cycle

easyAsked at Chime

Detect whether a singly linked list has a cycle using O(1) extra space.

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

Problem

Given the head of a linked list, determine if the list contains a cycle. A cycle exists when some node can be reached again by continuously following the next pointer. Return true if there is a cycle, false otherwise.

Constraints

  • 0 <= number of nodes <= 10^4
  • -10^5 <= Node.val <= 10^5
  • pos is -1 or a valid index in the list.

Examples

Example 1

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

Example 2

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

Approaches

1. Hash set of visited

Walk the list and record visited nodes; if any node repeats, there is a cycle.

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

Tradeoff:

2. Floyd tortoise and hare

Advance a slow pointer one step and a fast pointer two steps; they meet inside any cycle. Uses O(1) extra space.

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:

Chime-specific tips

Chime engineers look for the two-pointer pattern because their ACH retry queues are linked structures where memory-bounded cycle detection prevents infinite reprocessing of a stuck payment.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →