141. Linked List Cycle

Q: Why will slow and fast always meet if there is a cycle?

Once both pointers enter the cycle, fast is behind slow by some distance d. Each step fast closes the gap by 1 (gains 2, slow gains 1). So they meet after at most cycle_length steps.

Q: Why check fast.next !== null?

fast.next.next requires fast.next to be non-null. If the list has an even number of non-cycle nodes, fast lands exactly on null, and fast.next would throw.

Q: Can the hash-set approach handle very large lists?

It works but uses O(n) memory. In embedded networking devices with limited RAM, Floyd's O(1) approach is strongly preferred.

easyAsked at Juniper Networks

Detect a cycle in a linked list using Floyd's tortoise-and-hare algorithm. Juniper asks this because routing protocol loops (BGP route reflector cycles, OSPF LSA re-flooding loops) are a real class of network failures — the same cycle-detection logic applies in protocol state machines.

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

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

Glassdoor (2026-Q1)— Juniper SWE onsite reports mention cycle detection as a recurring linked-list question.
Blind (2025-11)— Multiple Juniper threads list Floyd's cycle detection as a must-know algorithm for Juniper SWE interviews.

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 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 given only as metadata — the list itself is the input).

Examples

Example 1

Input

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

Output

true

Explanation: Tail connects back to node at index 1, forming a cycle.

Example 2

Input

head = [1,2], pos = 0

Output

true

Explanation: Tail connects back to head.

Example 3

Input

head = [1], pos = -1

Output

false

Explanation: No cycle, single node.

Approaches

1. Hash set — O(n) space

Track visited nodes in a Set. If a node is encountered twice, 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 space. Simple and correct but uses extra memory proportional to the list size.

2. Floyd's tortoise-and-hare — O(1) space

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

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; // pointers met — cycle detected
  }
  return false;
}

Tradeoff: O(n) time, O(1) space. Floyd's algorithm. Fast is always ahead of slow; if a cycle exists, fast will lap slow and they will meet inside the cycle. This is the canonical answer Juniper expects.

Juniper Networks-specific tips

Name Floyd's algorithm explicitly — Juniper interviewers respect canonical algorithm names. Explain the intuition: inside a cycle, the fast pointer gains one step on the slow pointer per iteration, so they are guaranteed to meet in O(cycle length) steps. Connect to routing: detecting BGP routing loops follows the same principle of tracking state transitions to identify revisited states. The O(1) space solution is preferred for memory-constrained device software.

Common mistakes

Not checking fast.next !== null before fast.next.next — causes a null dereference when the list has an even number of nodes and no cycle.
Comparing node values instead of node references — two different nodes can have the same value; cycle detection requires reference equality.
Using slow === fast before advancing the pointers — they both start at head, so the check must come after moving.
Returning false before the loop exits — the loop termination condition (fast reaches null) is the no-cycle signal.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

Linked List Cycle II (LC 142) — find the exact node where the cycle begins.
Find the Duplicate Number (LC 287) — the same Floyd's algorithm applied to an array as a virtual linked list.
How would you detect a routing loop in a BGP route advertisement path?

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 will slow and fast always meet if there is a cycle?

Once both pointers enter the cycle, fast is behind slow by some distance d. Each step fast closes the gap by 1 (gains 2, slow gains 1). So they meet after at most cycle_length steps.

Why check fast.next !== null?

fast.next.next requires fast.next to be non-null. If the list has an even number of non-cycle nodes, fast lands exactly on null, and fast.next would throw.

Can the hash-set approach handle very large lists?

It works but uses O(n) memory. In embedded networking devices with limited RAM, Floyd's O(1) approach is strongly preferred.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →