141. Linked List Cycle
easyAsked at Juniper NetworksDetect 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 Sam K., Founder, InterviewChamp.AI · Last verified
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
head = [3,2,0,-4], pos = 1trueExplanation: Tail connects back to node at index 1, forming a cycle.
Example 2
head = [1,2], pos = 0trueExplanation: Tail connects back to head.
Example 3
head = [1], pos = -1falseExplanation: 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.
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.