Skip to main content

6. Linked List Cycle

easyAsked at JetBrains

Detect whether a linked list contains a cycle — JetBrains uses this to gauge whether you can spot graph cycles in symbol-resolution chains.

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

Problem

Given head of a linked list, determine if the list has a cycle. A cycle exists if any node can be reached again by continuously following the next pointer.

Constraints

  • 0 <= nodes <= 10^4
  • -10^5 <= Node.val <= 10^5

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. Visited set

Walk the list and remember every node; if you see one twice, there's a cycle.

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

Tradeoff:

2. Floyd's tortoise and hare

Advance slow by one and fast by two; they meet inside a cycle. JetBrains values this for the constant-space cycle detection used in resolver chains.

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:

JetBrains-specific tips

JetBrains expects you to connect this to detecting cyclic imports or self-referencing type aliases — explicitly say "this is how a resolver should detect circular references in O(1) memory."

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 JetBrains interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →