141. Linked List Cycle

Q: Why does Floyd's algorithm guarantee the pointers meet?

In a cycle of length L, the fast pointer gains one step per iteration relative to the slow pointer. After at most L iterations the distance between them becomes 0 mod L, i.e., they occupy the same node.

Q: Is the hash-set approach acceptable at Broadcom?

As an initial answer, yes. But expect the interviewer to ask for O(1) space — always follow up with Floyd's.

Q: How do you find the cycle entry node after detecting a cycle?

Reset slow to head. Advance both slow and fast one step at a time. They meet at the cycle entry — a result that follows from modular arithmetic on the cycle and pre-cycle lengths.

easyAsked at Broadcom

Detect whether a linked list contains a cycle. Broadcom tests this because cycle detection is a foundational technique in routing-loop detection — a real operational concern in Broadcom's switch and router ASIC software for protocols like STP and BGP path validation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

Glassdoor (2026-Q1)— Listed in Broadcom SWE interview reports for networking software roles as a pointer-technique question.
Blind (2025-11)— Broadcom candidates report cycle detection as a frequent early question paired with linked-list reversal.

Problem

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

Constraints

The number of the nodes in the list is in the range [0, 10^4].
−10^5 <= Node.val <= 10^5.
pos is -1 or a valid index in the linked list (pos is not given as a parameter, only for explanation).

Examples

Example 1

Input

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

Output

true

Explanation: The tail's next pointer links back to node index 1, forming a cycle.

Example 2

Input

head = [1,2], pos = 0

Output

true

Explanation: The tail links back to the head.

Example 3

Input

head = [1], pos = -1

Output

false

Explanation: Single node with no cycle.

Approaches

1. Hash set (visited tracking)

Store each visited node reference in a Set. If you encounter a node already in the Set, a cycle exists.

Time: O(n)
Space: O(n)

function hasCycle(head) {
  const seen = new Set();
  let curr = head;
  while (curr !== null) {
    if (seen.has(curr)) return true;
    seen.add(curr);
    curr = curr.next;
  }
  return false;
}

Tradeoff: O(n) time and O(n) space. Correct but uses extra memory. Mention this first, then offer Floyd's as the O(1) space improvement.

2. Floyd's tortoise and hare

Use two pointers: slow advances one step, fast advances two. If there is a cycle they will eventually meet. If fast reaches null, no cycle exists.

Time: O(n)
Space: O(1)

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Tradeoff: O(n) time, O(1) space. This is the canonical answer Broadcom expects. The two-pointer technique generalises to finding the cycle entry point (LC 142) — a natural follow-up.

Broadcom-specific tips

Name the algorithm: 'Floyd's cycle detection — tortoise and hare.' Explain the invariant in one sentence: 'In a cycle, the fast pointer laps the slow pointer; they must meet.' At Broadcom, connect this to networking: 'This is the algorithmic basis of TTL-based loop detection in IP forwarding — if you keep circulating, something is wrong.' The follow-up asking for the cycle entry node (LC 142) is nearly guaranteed.

Common mistakes

Checking slow === fast before any movement — they both start at head so they'd immediately return true incorrectly.
Not checking fast.next !== null before fast.next.next — causes null-dereference.
Using node values instead of node references for the visited check — values may repeat in valid acyclic lists.
Not handling head === null before starting the traversal.

Follow-up questions

An interviewer at Broadcom may pivot to one of these next:

Find the start node of the cycle (LC 142) — a classic two-pointer math extension.
Find the length of the cycle once detected.
Detect a cycle in a directed graph (DFS with coloring).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does Floyd's algorithm guarantee the pointers meet?

In a cycle of length L, the fast pointer gains one step per iteration relative to the slow pointer. After at most L iterations the distance between them becomes 0 mod L, i.e., they occupy the same node.

Is the hash-set approach acceptable at Broadcom?

As an initial answer, yes. But expect the interviewer to ask for O(1) space — always follow up with Floyd's.

How do you find the cycle entry node after detecting a cycle?

Reset slow to head. Advance both slow and fast one step at a time. They meet at the cycle entry — a result that follows from modular arithmetic on the cycle and pre-cycle lengths.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →