Skip to main content

9. Linked List Cycle

easyAsked at Baidu

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

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

Problem

Given the head of a linked list, return true if the list has a cycle in it. There is a cycle if some node in the list can be reached again by continuously following the next pointer.

Constraints

  • Number of nodes is in [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

Example 2

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

Approaches

1. Hash set of visited nodes

Walk the list; if you revisit any node reference, there is 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 tortoise and hare

Two pointers, slow advances by 1 and fast by 2; they meet iff a cycle exists.

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:

Baidu-specific tips

Baidu uses cycle detection on the crawler frontier graph to catch redirect loops, so they reward Floyd's two-pointer pattern over any visited-set solution that scales linearly in 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 Baidu interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →