You're given the head of a singly linked list. Each node has a value and a next pointer. In a clean list, walking next pointers eventually lands you on null — the list ends. In a cyclic list, walking next eventually lands you back on a node you've already visited, and the walk never terminates. Your job is to return true if the list contains a cycle, false otherwise — using O(1) extra space.
type Node = { value: unknown; next: Node | null };
// Returns true if walking `next` from head ever revisits a node.
// Returns false if the walk terminates at `null`.
function linkedListDetectCycle(head: Node | null): boolean;// Clean linear list: 1 -> 2 -> 3 -> null
const a = { value: 1, next: null };
const b = { value: 2, next: null };
const c = { value: 3, next: null };
a.next = b; b.next = c;
linkedListDetectCycle(a); // false// Tail loops back to the head: 1 -> 2 -> 3 -> 1 -> ...
const a = { value: 1, next: null };
const b = { value: 2, next: null };
const c = { value: 3, next: null };
a.next = b; b.next = c; c.next = a;
linkedListDetectCycle(a); // true// Tail loops to the middle: 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> ...
linkedListDetectCycle(headOfThatList); // true// Empty list and self-loops.
linkedListDetectCycle(null); // false
const x = { value: 1, next: null }; x.next = x;
linkedListDetectCycle(x); // true=== true and === false. Don't return the cycle start node, the cycle length, or a truthy/falsy value of another shape.Set or Map of visited nodes — that's O(n) and the test for a 1000-node list checks that your solution stays linear in time but doesn't keep growing memory.visited = true flag (or rewrites next) destroys the caller's data. There's an explicit test that the input list is byte-for-byte unchanged after the call.null head is valid input. An empty list trivially has no cycle — return false, don't throw.head.next === head). All three are real cycles.You'll write a function that decides whether walking next from head eventually loops back on itself — using two pointers and constant extra memory.
You're given the head of a singly linked list. Most lists end: keep following next and you eventually hit null. Some lists don't — somewhere down the line, a node's next points back to an earlier node, and the walk loops forever. You need to return true for those, false for the clean ones. The catch: you have to do it without keeping a Set of every node you've seen — that's O(n) extra memory, and for a list of a million nodes that's a million references your function is hoarding. The constraint forces you into a smarter algorithm.
Imagine two people walking the same path. One walks at a normal pace (one node per step), the other runs at double speed (two nodes per step). If the path is a straight line that ends, the runner reaches the end first and you stop. If the path loops, both will eventually be inside the loop — and then the runner gains exactly one node of ground per step. Sooner or later they're standing on the same node. That's the cycle, detected.
The shape of the input matters here. A "cycle" in this problem isn't necessarily the whole list — it's a prefix leading into a loop. The tail node's next points back somewhere inside that loop. Self-loops (head.next === head) and full-list loops (tail → head) are just the degenerate cases.
The instinct most people reach for first: remember every node you've already visited, and stop when you see one twice.
function naive(head) {
const seen = new Set();
let cur = head;
while (cur !== null) {
if (seen.has(cur)) return true; // revisit -> cycle
seen.add(cur);
cur = cur.next;
}
return false; // walked off the end -> no cycle
}It's correct. It runs in O(n) time. The problem is the seen Set — it holds a reference to every node you've walked past. For a million-node list with no cycle, your function allocates a million-entry Set just to confirm "no cycle here." The prompt explicitly forbids this — the constraint is O(1) extra space, and one of the tests is a 2000-node list that you must walk without unbounded growth. The first attempt fails the design constraint, not the correctness tests, but the constraint is the whole point of the question.
function linkedListDetectCycle(head) {
// Two pointers starting at the same place. Both walk forward — slow
// takes one step per iteration, fast takes two. If the list ends,
// fast hits null first; if the list cycles, fast eventually laps slow.
let slow = head;
let fast = head;
// The loop condition checks `fast` and `fast.next` because each iteration
// does `fast.next.next` — if either is null, we've reached the end and
// there's no cycle. Checking only `fast` would let us read `.next` of
// a node whose `next` is null and crash on the second hop.
while (fast !== null && fast.next !== null) {
slow = slow.next; // one step
fast = fast.next.next; // two steps
// We compare references, not values — two distinct nodes can hold the
// same `value` and that's fine. The cycle is structural: the SAME node
// is reachable from itself by walking `next` some number of times.
if (slow === fast) return true;
}
// `fast` ran off the end (null), so there's a terminator — no cycle.
return false;
}
module.exports = { linkedListDetectCycle };Three shifts from the naive version. First, no Set. All we keep is two local variables — slow and fast — which is the O(1) extra space the constraint demands. Second, the termination test is fast and fast.next, not slow. If a cycle exists, fast is always at least as far along as slow, so checking the leading pointer is the earlier signal. The fast.next half of the check guards the second hop of fast.next.next — without it, a two-node list a -> b -> null would crash because we'd try to read b.next.next and b.next is null. Third, the equality test is reference identity (===), not deep equality on .value. Two distinct nodes with the same value are not a cycle; the cycle exists only when the literal same node turns up twice on the walk.
Why does this work at all? Once both pointers are inside the cycle, the gap between them (measured forward, modulo cycle length L) grows by exactly one per iteration — slow adds 1, fast adds 2, net +1. After at most L iterations the gap wraps around to zero and they collide. This is Floyd's classic argument; the table below traces it on a concrete cycle of length 4.
Trace linkedListDetectCycle(head) on this list: five nodes [1, 2, 3, 4, 5] where 5.next points back to node 3 (so the cycle is 3 -> 4 -> 5 -> 3 -> ..., a loop of length 3 hanging off a prefix of length 2).
Initial. slow = node1, fast = node1. Both at the head.
Iteration 1. fast is node1, fast.next is node2, both non-null — enter the body. slow = node2. fast = node3 (one hop to node2, second hop to node3). slow === fast? node2 === node3 — no.
Iteration 2. fast is node3, fast.next is node4 — enter. slow = node3. fast = node5 (node3 → node4 → node5). node3 === node5? No.
Iteration 3. fast is node5, fast.next is node3 (the cycle edge) — enter. slow = node4. fast = node4 (node5 → node3 → node4). node4 === node4? Yes. Return true.
Total iterations: 3. The list has 5 nodes and a loop of length 3 — the algorithm did O(n) work and used zero allocations beyond the two pointers. For contrast, if the test list were instead [1, 2, 3, 4, 5] with 5.next = null, iteration 2 would set fast = node5, iteration 3 would find fast.next === null and exit the loop, and the function would return false after the same three iterations.
fast in the loop condition. Write while (fast !== null) and the body's fast.next.next blows up on any list of length two with no cycle: slow = node2, then fast = node2.next.next dereferences null.next. You need fast !== null && fast.next !== null — both, in that order, short-circuited.node.visited = true. This would work for detection — you'd return true the moment you see a node you've already tagged — but it mutates the caller's data. The test that snapshots node keys before and after the call will catch it. The fix is to never touch the nodes; use pointer identity instead.slow.value === fast.value instead of slow === fast. Reference identity is what defines a cycle. Two distinct nodes can hold the value 1, and that doesn't make them the same node. Test: a clean list [1, 1, 1] — value-equal at every step but no cycle. Compare references.while loop.true. Tests use toBe(true) and toBe(false), which are strict. Returning 1 or the cycle-start node passes a toBeTruthy test but fails toBe(true). Return the boolean.slow and fast meet, reset one pointer to head and advance both one step at a time. They meet again at the cycle's entry node — a small modular-arithmetic miracle that falls out of the same mu/L setup from the cycle-structure diagram. This is the variant LeetCode asks as "Linked List Cycle II."fast still and walk slow one step at a time until they meet again. The number of steps is exactly L, the cycle length. Useful when you need to know "how big is the loop" — e.g., for layout debugging when an algorithm accidentally builds one.O(n) time with O(1) space but typically runs ~25% fewer iterations than Floyd's. It restarts the slow pointer at exponentially growing intervals instead of always moving in lockstep. Worth reading if you're optimising hot-path cycle detection in a real system.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You're given the head of a singly linked list. Each node has a value and a next pointer. In a clean list, walking next pointers eventually lands you on null — the list ends. In a cyclic list, walking next eventually lands you back on a node you've already visited, and the walk never terminates. Your job is to return true if the list contains a cycle, false otherwise — using O(1) extra space.
type Node = { value: unknown; next: Node | null };
// Returns true if walking `next` from head ever revisits a node.
// Returns false if the walk terminates at `null`.
function linkedListDetectCycle(head: Node | null): boolean;// Clean linear list: 1 -> 2 -> 3 -> null
const a = { value: 1, next: null };
const b = { value: 2, next: null };
const c = { value: 3, next: null };
a.next = b; b.next = c;
linkedListDetectCycle(a); // false// Tail loops back to the head: 1 -> 2 -> 3 -> 1 -> ...
const a = { value: 1, next: null };
const b = { value: 2, next: null };
const c = { value: 3, next: null };
a.next = b; b.next = c; c.next = a;
linkedListDetectCycle(a); // true// Tail loops to the middle: 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> ...
linkedListDetectCycle(headOfThatList); // true// Empty list and self-loops.
linkedListDetectCycle(null); // false
const x = { value: 1, next: null }; x.next = x;
linkedListDetectCycle(x); // true=== true and === false. Don't return the cycle start node, the cycle length, or a truthy/falsy value of another shape.Set or Map of visited nodes — that's O(n) and the test for a 1000-node list checks that your solution stays linear in time but doesn't keep growing memory.visited = true flag (or rewrites next) destroys the caller's data. There's an explicit test that the input list is byte-for-byte unchanged after the call.null head is valid input. An empty list trivially has no cycle — return false, don't throw.head.next === head). All three are real cycles.You'll write a function that decides whether walking next from head eventually loops back on itself — using two pointers and constant extra memory.
You're given the head of a singly linked list. Most lists end: keep following next and you eventually hit null. Some lists don't — somewhere down the line, a node's next points back to an earlier node, and the walk loops forever. You need to return true for those, false for the clean ones. The catch: you have to do it without keeping a Set of every node you've seen — that's O(n) extra memory, and for a list of a million nodes that's a million references your function is hoarding. The constraint forces you into a smarter algorithm.
Imagine two people walking the same path. One walks at a normal pace (one node per step), the other runs at double speed (two nodes per step). If the path is a straight line that ends, the runner reaches the end first and you stop. If the path loops, both will eventually be inside the loop — and then the runner gains exactly one node of ground per step. Sooner or later they're standing on the same node. That's the cycle, detected.
The shape of the input matters here. A "cycle" in this problem isn't necessarily the whole list — it's a prefix leading into a loop. The tail node's next points back somewhere inside that loop. Self-loops (head.next === head) and full-list loops (tail → head) are just the degenerate cases.
The instinct most people reach for first: remember every node you've already visited, and stop when you see one twice.
function naive(head) {
const seen = new Set();
let cur = head;
while (cur !== null) {
if (seen.has(cur)) return true; // revisit -> cycle
seen.add(cur);
cur = cur.next;
}
return false; // walked off the end -> no cycle
}It's correct. It runs in O(n) time. The problem is the seen Set — it holds a reference to every node you've walked past. For a million-node list with no cycle, your function allocates a million-entry Set just to confirm "no cycle here." The prompt explicitly forbids this — the constraint is O(1) extra space, and one of the tests is a 2000-node list that you must walk without unbounded growth. The first attempt fails the design constraint, not the correctness tests, but the constraint is the whole point of the question.
function linkedListDetectCycle(head) {
// Two pointers starting at the same place. Both walk forward — slow
// takes one step per iteration, fast takes two. If the list ends,
// fast hits null first; if the list cycles, fast eventually laps slow.
let slow = head;
let fast = head;
// The loop condition checks `fast` and `fast.next` because each iteration
// does `fast.next.next` — if either is null, we've reached the end and
// there's no cycle. Checking only `fast` would let us read `.next` of
// a node whose `next` is null and crash on the second hop.
while (fast !== null && fast.next !== null) {
slow = slow.next; // one step
fast = fast.next.next; // two steps
// We compare references, not values — two distinct nodes can hold the
// same `value` and that's fine. The cycle is structural: the SAME node
// is reachable from itself by walking `next` some number of times.
if (slow === fast) return true;
}
// `fast` ran off the end (null), so there's a terminator — no cycle.
return false;
}
module.exports = { linkedListDetectCycle };Three shifts from the naive version. First, no Set. All we keep is two local variables — slow and fast — which is the O(1) extra space the constraint demands. Second, the termination test is fast and fast.next, not slow. If a cycle exists, fast is always at least as far along as slow, so checking the leading pointer is the earlier signal. The fast.next half of the check guards the second hop of fast.next.next — without it, a two-node list a -> b -> null would crash because we'd try to read b.next.next and b.next is null. Third, the equality test is reference identity (===), not deep equality on .value. Two distinct nodes with the same value are not a cycle; the cycle exists only when the literal same node turns up twice on the walk.
Why does this work at all? Once both pointers are inside the cycle, the gap between them (measured forward, modulo cycle length L) grows by exactly one per iteration — slow adds 1, fast adds 2, net +1. After at most L iterations the gap wraps around to zero and they collide. This is Floyd's classic argument; the table below traces it on a concrete cycle of length 4.
Trace linkedListDetectCycle(head) on this list: five nodes [1, 2, 3, 4, 5] where 5.next points back to node 3 (so the cycle is 3 -> 4 -> 5 -> 3 -> ..., a loop of length 3 hanging off a prefix of length 2).
Initial. slow = node1, fast = node1. Both at the head.
Iteration 1. fast is node1, fast.next is node2, both non-null — enter the body. slow = node2. fast = node3 (one hop to node2, second hop to node3). slow === fast? node2 === node3 — no.
Iteration 2. fast is node3, fast.next is node4 — enter. slow = node3. fast = node5 (node3 → node4 → node5). node3 === node5? No.
Iteration 3. fast is node5, fast.next is node3 (the cycle edge) — enter. slow = node4. fast = node4 (node5 → node3 → node4). node4 === node4? Yes. Return true.
Total iterations: 3. The list has 5 nodes and a loop of length 3 — the algorithm did O(n) work and used zero allocations beyond the two pointers. For contrast, if the test list were instead [1, 2, 3, 4, 5] with 5.next = null, iteration 2 would set fast = node5, iteration 3 would find fast.next === null and exit the loop, and the function would return false after the same three iterations.
fast in the loop condition. Write while (fast !== null) and the body's fast.next.next blows up on any list of length two with no cycle: slow = node2, then fast = node2.next.next dereferences null.next. You need fast !== null && fast.next !== null — both, in that order, short-circuited.node.visited = true. This would work for detection — you'd return true the moment you see a node you've already tagged — but it mutates the caller's data. The test that snapshots node keys before and after the call will catch it. The fix is to never touch the nodes; use pointer identity instead.slow.value === fast.value instead of slow === fast. Reference identity is what defines a cycle. Two distinct nodes can hold the value 1, and that doesn't make them the same node. Test: a clean list [1, 1, 1] — value-equal at every step but no cycle. Compare references.while loop.true. Tests use toBe(true) and toBe(false), which are strict. Returning 1 or the cycle-start node passes a toBeTruthy test but fails toBe(true). Return the boolean.slow and fast meet, reset one pointer to head and advance both one step at a time. They meet again at the cycle's entry node — a small modular-arithmetic miracle that falls out of the same mu/L setup from the cycle-structure diagram. This is the variant LeetCode asks as "Linked List Cycle II."fast still and walk slow one step at a time until they meet again. The number of steps is exactly L, the cycle length. Useful when you need to know "how big is the loop" — e.g., for layout debugging when an algorithm accidentally builds one.O(n) time with O(1) space but typically runs ~25% fewer iterations than Floyd's. It restarts the slow pointer at exponentially growing intervals instead of always moving in lockstep. Worth reading if you're optimising hot-path cycle detection in a real system.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.