Skip to main content

14. Linked List Cycle

easyAsked at GitLab

Detect whether a singly linked list contains a cycle using O(1) extra memory.

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

Problem

Given the head of a singly linked list, return true if the list contains a cycle and false otherwise. You may not modify the list.

Constraints

  • 0 <= nodes <= 10^4
  • -10^5 <= 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, remembering each node reference; if we revisit one, it'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 slow/fast

Move slow by one, fast by two — if they meet, the list has a cycle; if fast hits null, it doesn't.

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:

GitLab-specific tips

GitLab frames this as a CI-graph integrity check — they want to see Floyd's pointers because a permission-inheritance chain or pipeline-needs graph must reject cyclic configurations cheaply.

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

Practice these live with InterviewChamp.AI →