Skip to main content

8. Linked List Cycle

easyAsked at Swiggy

Detect whether a singly linked list contains a cycle.

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

Problem

Given head of a linked list, return true if the list contains a cycle (some node's next points back to an earlier node), else return false. Try to do it in O(1) extra space.

Constraints

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

Examples

Example 1

Input
head=[3,2,0,-4] with tail->index 1
Output
true

Example 2

Input
head=[1,2] linear
Output
false

Approaches

1. Visited set

Walk list and record visited nodes.

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

Tradeoff:

2. Floyd tortoise and hare

Two pointers, slow advances by 1 and fast by 2. If a cycle exists they meet inside it; otherwise fast hits null. Constant 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:

Swiggy-specific tips

Swiggy uses cycle detection to gauge whether you can reason about courier-route graphs that may form loops when assignments stack up incorrectly.

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

Practice these live with InterviewChamp.AI →