idx 0
slow
Detect whether a linked list contains a cycle using Floyd's tortoise-and-hare algorithm — two pointers moving at different speeds will inevitably meet inside any cycle, requiring O(1) extra space and a single pass.
Given the head of a singly-linked list, return trueif the list contains a cycle (some node's next pointer eventually leads back to a previously-visited node) and false otherwise. Example: list 3 → 2 → 0 → -4 → (back to 2) → true. List 1 → 2 → null → false.
null first. No extra memory beyond two pointers.slow = head and fast = head. Both start at the same node.fast !== null && fast.next !== null. If either is null, there is no cycle — a null pointer can't wrap back.slow = slow.next (1 step) and fast = fast.next.next (2 steps). Fast gains on slow by exactly 1 node per iteration inside a cycle.slow === fast (same node object, not just same value), a cycle exists — return true.fast hitting null — no cycle. Return false.slow === fast), not value equality. Two different nodes can hold the same integer value; only the same node object proves a cycle.Once both pointers are in the cycle, think of fast's lead over slow decreasing by 1 each step (in the cycle's frame of reference). Because the cycle is finite, the lead reaches 0 — they meet — within at most c steps (cycle length).
4 nodes. Tail links back to index 1 (cycle). Place slow and fast at head (index 0).// Definition for singly-linked list.
// class ListNode {
// val: number;
// next: ListNode | null;
// constructor(val?: number, next?: ListNode | null) {
// this.val = val ?? 0;
// this.next = next ?? null;
// }
// }
function hasCycle(head: ListNode | null): boolean {
let slow: ListNode | null = head;
let fast: ListNode | null = head;
while (fast !== null && fast.next !== null) {
slow = slow!.next; // advance 1
fast = fast.next.next; // advance 2
if (slow === fast) return true; // pointers met — cycle
}
return false; // fast fell off end — no cycle
}slow and fast begin at head. Starting them at the same node is safe; the first iteration separates them before the equality check.fast !== null && fast.next !== null before advancing. If fast is null or its next is null, the list terminates — no cycle possible. We never dereference a null pointer.slow moves one step; fastmoves two. Inside a cycle, fast gains one node on slow per iteration, guaranteeing they meet within the cycle's length.slow === fast is a reference comparison — same node object. When they point to the same node, a cycle is confirmed.fast (or fast.next) was null — the list has a proper end. Return false.head and advance both one step at a time — they meet at the cycle entry (LC 142).true on first repeat. Simpler code but O(n) space vs O(1) for fast/slow.| detect a cycle in a linked list | fast & slow pointers (Floyd) |
| O(1) space cycle / loop detection | two-pointer speed difference |
| "does the sequence revisit a state?" | implicit list + fast/slow |
| find the middle of a linked list | fast runs 2×; slow lands at mid |
function hasCycle(head: ListNode | null): boolean {
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;
}fast !== null && fast.next !== null. Why must both be checked?