Linked List Cycle (LeetCode 141)
You're given head, the first node of a linked list. Figure out whether the list loops back on itself anywhere — that is, whether repeatedly following next pointers can revisit a node you've already seen.
(Internally the test harness marks such a loop with an index pos pointing at the node the tail wraps back to — or -1 if there's no loop — but your function never receives pos directly.)
Return true if a cycle exists, false otherwise.
Worked Examples
head = [3,2,0,-4], pos = 1trueSlow advances 1 step (slow = slow.next) while Fast advances 2 steps (fast = fast.next.next). The distance between them decreases by 1 on every cycle iteration.
Upon collision inside the loop, moving one pointer back to the list head and advancing both at 1 step guarantees they will collide at the exact cycle entrance node.
head = [1,2], pos = 0truehead = [1], pos = -1false⚖️Formal Constraints & Bounds
The number of the nodes in the list is in the range
[0, 104].-105 <= Node.val <= 105posis-1or a valid index in the linked-list.
Core Insight
Inside a cycle of length C, the relative gap between fast (2 hops) and slow (1 hop) decreases by exactly 1 each turn, guaranteeing collision in at most C steps.
Real-World Scenario & Production Applications
Memory leak detection in reference-counted pointer graphs and cyclic deadlock detection in distributed transaction coordinators.
Step-by-Step Execution Trace Table
| Tick / Iteration | Slow Pointer (slow.val) | Fast Pointer (fast.val) | Fast Traversal Step | Condition Check (slow == fast) |
|---|---|---|---|---|
| Init | Node(3) [index 0] | Node(3) [index 0] | Pointers initialized at head | Loop begins: slow != fast check after move |
| 1 | Node(2) [index 1] | Node(0) [index 2] | slow advances 1; fast advances 2 (3 -> 2 -> 0) | Node(2) != Node(0) Continue |
| 2 | Node(0) [index 2] | Node(2) [index 1] | slow advances 1; fast wraps cycle (0 -> -4 -> 2) | Node(0) != Node(2) Continue |
| 3 | Node(-4) [index 3] | Node(-4) [index 3] | slow advances 1; fast advances 2 (2 -> 0 -> -4) | Node(-4) == Node(-4) Cycle Detected (True) |
| 1 | slow, fast = head, head |
| 2 | while fast and fast.next: |
| 3 | slow = slow.next |
| 4 | fast = fast.next.next |
| 5 | if slow == fast: |
| 6 | return True |
| 7 | return False |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Two runners on the same looping track, moving at different speeds, will always eventually meet — that guarantee is the entire algorithm.
🏟️ The Analogy: Two Runners on a Circular Track
Picture two runners on a circular track: a jogger and a sprinter moving exactly twice as fast. If the track were a straight, endless road, the sprinter would just pull ahead forever and the two would never meet again. But on a loop, the sprinter eventually laps the jogger from behind — and "getting lapped" is really just "the gap between them, which shrinks by one step every round, eventually hits zero." If there's no loop at all — just a straight dead-end road — the sprinter simply runs off the end, and no meeting ever happens.
🔑 The Key Idea in the Code
Because fast closes the gap to slow by exactly one node every single step once both are inside a cycle, the collision isn't a matter of luck — it's mathematically guaranteed to happen within one full lap of the cycle.
Dereferencing null on
fast.next: Always guardwhile fast and fast.next:before advancingfast = fast.next.next. Checking onlywhile fast:crashes on even-length lists.Comparing node values instead of node identities: In cyclic lists, two distinct nodes may have identical
.val. You must compare node references (slow is fast), not values (slow.val == fast.val).Starting both pointers at head with
while slow != fast: If both start athead, the while conditionwhile slow != fastterminates before taking a single step. Advance pointers once or initializefast = head.next.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Linked list or functional sequence + cycle detection + O(1) space constraint.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: within a cycle of length C, fast gains 1 step per iteration on slow, guaranteeing collision within C steps.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I initialize slow = head and fast = head. In a loop, slow moves 1 step and fast moves 2 steps. If fast or fast.next is null, no cycle exists. If slow == fast, a cycle is detected. Runs in
O(N)time withO(1)auxiliary space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Slow moves 1 step, fast moves 2 steps. If cycle of length K exists, distance between fast and slow decreases by 1 each step, meeting in at most N iterations.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only stores two pointer references in O(1) auxiliary space.
T(N) ≤ N + K = O(N)
Derivation Progression
Distance closes by 1 step each loop
In each step, fast gains 1 node on slow within a cycle of length K.
≤ K ≤ N steps to meet
Pointers must intersect within K cycles after slow enters the loop.
O(N) total node hops
Terminates in O(N) operations whether cycle exists or not.
Variable Definitions
Total number of nodes in the linked list
Length of cycle (if cycle exists)
Memory Architecture & Bounds
O(1) Iterative
O(1) Two node pointers
O(1) Boolean return
Boundary Best / Worst Cases
if no cycle on small list.
.
if cycle is at end.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "determine if linked list has a cycle", "can you solve it using O(1) memory?". Floyd's Cycle Finding Algorithm (Tortoise and Hare).
Number of nodes . Requires strictly time and auxiliary memory.
Null checks: must check while fast and fast.next to avoid dereferencing fast.next.next on acyclic lists. Empty list or single node without cycle returns False safely.
Linked List Cycle (LeetCode 141)
You're given head, the first node of a linked list. Figure out whether the list loops back on itself anywhere — that is, whether repeatedly following next pointers can revisit a node you've already seen.
(Internally the test harness marks such a loop with an index pos pointing at the node the tail wraps back to — or -1 if there's no loop — but your function never receives pos directly.)
Return true if a cycle exists, false otherwise.
Worked Examples
head = [3,2,0,-4], pos = 1trueSlow advances 1 step (slow = slow.next) while Fast advances 2 steps (fast = fast.next.next). The distance between them decreases by 1 on every cycle iteration.
Upon collision inside the loop, moving one pointer back to the list head and advancing both at 1 step guarantees they will collide at the exact cycle entrance node.
head = [1,2], pos = 0truehead = [1], pos = -1false⚖️Formal Constraints & Bounds
The number of the nodes in the list is in the range
[0, 104].-105 <= Node.val <= 105posis-1or a valid index in the linked-list.
Core Insight
Inside a cycle of length C, the relative gap between fast (2 hops) and slow (1 hop) decreases by exactly 1 each turn, guaranteeing collision in at most C steps.
Real-World Scenario & Production Applications
Memory leak detection in reference-counted pointer graphs and cyclic deadlock detection in distributed transaction coordinators.
Step-by-Step Execution Trace Table
| Tick / Iteration | Slow Pointer (slow.val) | Fast Pointer (fast.val) | Fast Traversal Step | Condition Check (slow == fast) |
|---|---|---|---|---|
| Init | Node(3) [index 0] | Node(3) [index 0] | Pointers initialized at head | Loop begins: slow != fast check after move |
| 1 | Node(2) [index 1] | Node(0) [index 2] | slow advances 1; fast advances 2 (3 -> 2 -> 0) | Node(2) != Node(0) Continue |
| 2 | Node(0) [index 2] | Node(2) [index 1] | slow advances 1; fast wraps cycle (0 -> -4 -> 2) | Node(0) != Node(2) Continue |
| 3 | Node(-4) [index 3] | Node(-4) [index 3] | slow advances 1; fast advances 2 (2 -> 0 -> -4) | Node(-4) == Node(-4) Cycle Detected (True) |
| 1 | slow, fast = head, head |
| 2 | while fast and fast.next: |
| 3 | slow = slow.next |
| 4 | fast = fast.next.next |
| 5 | if slow == fast: |
| 6 | return True |
| 7 | return False |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Two runners on the same looping track, moving at different speeds, will always eventually meet — that guarantee is the entire algorithm.
🏟️ The Analogy: Two Runners on a Circular Track
Picture two runners on a circular track: a jogger and a sprinter moving exactly twice as fast. If the track were a straight, endless road, the sprinter would just pull ahead forever and the two would never meet again. But on a loop, the sprinter eventually laps the jogger from behind — and "getting lapped" is really just "the gap between them, which shrinks by one step every round, eventually hits zero." If there's no loop at all — just a straight dead-end road — the sprinter simply runs off the end, and no meeting ever happens.
🔑 The Key Idea in the Code
Because fast closes the gap to slow by exactly one node every single step once both are inside a cycle, the collision isn't a matter of luck — it's mathematically guaranteed to happen within one full lap of the cycle.
Dereferencing null on
fast.next: Always guardwhile fast and fast.next:before advancingfast = fast.next.next. Checking onlywhile fast:crashes on even-length lists.Comparing node values instead of node identities: In cyclic lists, two distinct nodes may have identical
.val. You must compare node references (slow is fast), not values (slow.val == fast.val).Starting both pointers at head with
while slow != fast: If both start athead, the while conditionwhile slow != fastterminates before taking a single step. Advance pointers once or initializefast = head.next.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Linked list or functional sequence + cycle detection + O(1) space constraint.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: within a cycle of length C, fast gains 1 step per iteration on slow, guaranteeing collision within C steps.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I initialize slow = head and fast = head. In a loop, slow moves 1 step and fast moves 2 steps. If fast or fast.next is null, no cycle exists. If slow == fast, a cycle is detected. Runs in
O(N)time withO(1)auxiliary space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Slow moves 1 step, fast moves 2 steps. If cycle of length K exists, distance between fast and slow decreases by 1 each step, meeting in at most N iterations.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only stores two pointer references in O(1) auxiliary space.
T(N) ≤ N + K = O(N)
Derivation Progression
Distance closes by 1 step each loop
In each step, fast gains 1 node on slow within a cycle of length K.
≤ K ≤ N steps to meet
Pointers must intersect within K cycles after slow enters the loop.
O(N) total node hops
Terminates in O(N) operations whether cycle exists or not.
Variable Definitions
Total number of nodes in the linked list
Length of cycle (if cycle exists)
Memory Architecture & Bounds
O(1) Iterative
O(1) Two node pointers
O(1) Boolean return
Boundary Best / Worst Cases
if no cycle on small list.
.
if cycle is at end.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "determine if linked list has a cycle", "can you solve it using O(1) memory?". Floyd's Cycle Finding Algorithm (Tortoise and Hare).
Number of nodes . Requires strictly time and auxiliary memory.
Null checks: must check while fast and fast.next to avoid dereferencing fast.next.next on acyclic lists. Empty list or single node without cycle returns False safely.