What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

22. Linked List Cycle II (Find Entry Node) • Invariant Proof & Speed-Run

Theory Context•Two Pointers & Sliding Window

MediumLC 142

Linked List Cycle II (LeetCode 142)

Target Frequency:AmazonMicrosoftGoogle

You're given the head of a linked list that may loop back on itself. Find and return the exact node where that loop begins — or null if the list has no loop at all.

(A test harness may describe the loop internally with a 0-indexed pos marking where the tail's next pointer reconnects, using -1 for no loop, but that index is never handed to your function.)

You must leave the linked list unmodified.

Worked Examples

Example 1

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

Output:tail connects to node index 1

Cyclic Linked List TopologyCycle at Node[1]

Floyd Cycle Detection

Access Road (L):1 node

Cycle Loop (C):3 nodes

Loop Entry:Node[1] (val: 2)

Collision / Meeting Point Detected!

Fast / Slow Pointer Invariant

Slow 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.

Cycle Origin Recovery ($L = kC - M$)

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.

Explanation: The tail node (-4) loops back into the node at index 1 (value 2), so that node is the cycle's entry point.

Example 2

Input:head = [1,2], pos = 0

Output:tail connects to node index 0

Explanation: The tail node (2) loops back into the node at index 0 (value 1), so that node is the cycle's entry point.

Example 3

Input:head = [1], pos = -1

Output:no cycle

Explanation: There is no cycle in the linked list.

⚖️Formal Constraints & Bounds

The number of the nodes in the list is in the range [0, 10⁴].
-10⁵ <= Node.val <= 10⁵
pos is -1 or a valid index in the linked-list.

Deep-Dive & Conceptual Insights

Core Insight

The distance from the head to the cycle origin equals the distance from the Phase 1 collision point to the cycle origin (L = k·C - x).

Real-World Scenario & Production Applications

Detecting circular dependencies in build systems, finding recurring loop states in state machines, and reference-counted garbage collection.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Phase 1 -- Fast & Slow Pointer Collision

Advance slow at 1x speed and fast at 2x speed until they collide inside the cycle loop, proving a cycle exists. If fast reaches null, terminate early.

Mathematical Recurrence / Code Invariant

slow, fast = head, head
while fast and fast.next:
    slow = slow.next; fast = fast.next.next
    if slow == fast: break
else: return None

Step-by-Step Execution Trace Table

Phase	Step	Ptr 1 Position	Ptr 2 Position	Distance / Action	Status
Phase 1: Rendezvous	1-3	`slow` at Node(-4)	`fast` at Node(-4)	Standard Floyd cycle detection	Rendezvous confirmed at Node(-4)
Phase 2: Origin Seek	Init	`p1 = head` (Node 3)	`p2 = meeting` (Node -4)	Reset one pointer to head; keep other at meeting node	Both step at uniform speed 1
Phase 2: Origin Seek	1	`p1 = p1.next` (Node 2)	`p2 = p2.next` (Node 2)	Step 1: `3 -> 2`; `-4 -> 2`	`p1 == p2`! Cycle entry is Node(2)

Worked on Paper

The Math, Step by Step

1. The distances in the list

Count distances in steps, where one step follows one next pointer. Name three numbers:

$a$ is the number of steps from head to the entrance, the first node of the cycle. This is the node the code must return.
$L$ is the cycle length, the number of nodes in the cycle. Walking $L$ steps inside the cycle brings you back to the same node.
$b$ is the number of steps from the entrance forward to the node where slow and fast meet, with $0 \le b < L$ .

The picture shows Example 1. The tail node $-4$ points back to the node with value 2 at index 1. So the entrance is index 1, $a = 1$ , and the cycle holds the three nodes 2, 0 and $-4$ , so $L = 3$ .

2. Where the two pointers are after $s$ rounds

Both pointers start at head. In every round of phase 1, slow moves 1 step and fast moves 2 steps. After $s$ rounds, slow has moved $s$ steps and fast has moved $2s$ steps.

The number of steps a pointer has moved decides where it stands. A pointer that moved fewer than $a$ steps is still before the cycle. A pointer that moved $t \ge a$ steps is inside the cycle, $(t - a) \bmod L$ steps past the entrance. Here $x \bmod L$ is the remainder after dividing $x$ by $L$ .

3. Why phase 2 stops at the entrance

Suppose the pointers meet after $s$ rounds. They stand on the same node inside the cycle. fast has moved $s$ steps more than slow. Two positions in the cycle are the same only when the difference in steps is a whole number of laps. So

$s = k \cdot L \quad \text{for some whole number } k \ge 1$

slow stands $b$ steps past the entrance, so $s - a$ and $b$ differ by whole laps: $s - a = b + j \cdot L$ for some whole number $j \ge 0$ . Put $s = k \cdot L$ into this equation:

$a + b = (k - j) \cdot L$

So $a + b$ is a whole number of laps. This is the key fact: walking $a$ steps forward from the meeting point ends at the entrance. The meeting point is $b$ steps past the entrance. Walking $a$ more steps puts a pointer $a + b$ steps past the entrance, which is a whole number of laps, so it is at the entrance again.

Phase 2 uses this fact. ptr1 starts at head, and ptr2 starts at the meeting point. Both move one step per round. After $a$ rounds, ptr1 reaches the entrance, because the entrance is $a$ steps from head. ptr2 also reaches the entrance, by the key fact. They cannot meet earlier. Before round $a$ , ptr1 is still outside the cycle, and ptr2 is always inside it.

4. Why phase 1 always ends, and the start at `head`

If the list has no cycle, fast reaches the end first. The loop while fast and fast.next stops, and the code returns None.

If the list has a cycle, slow enters it after $a$ rounds. fast is already inside. From then on, fast gains one step on slow in every round. The gap between them inside the cycle shrinks by one step per round, so it reaches $0$ within $L$ rounds. So phase 1 ends after at most $a + L$ rounds.

Both pointers must start at the same node, head. The proof in part 3 uses "fast has moved exactly twice as many steps as slow". If fast started at head.next, that rule would be off by one step. On Example 1 the two pointers of phase 2 would then never stand on the same node, so the loop while ptr1 != ptr2 would never end.

5. Example 1 by hand

head = [3,2,0,-4], pos = 1, so $a = 1$ and $L = 3$ . Nodes are named by index.

Round	`slow` moved	`slow` at	`fast` moved	`fast` at
1	1	index 1 (value 2)	2	index 2 (value 0)
2	2	index 2 (value 0)	4	index 1 (value 2)
3	3	index 3 (value $-4$ )	6	index 3 (value $-4$ )

The pointers meet after $s = 3$ rounds, which is $1 \cdot L$ . The meeting node, index 3, is $b = 2$ steps past the entrance. So $a + b = 1 + 2 = 3 = L$ , a whole lap. In phase 2, ptr1 moves from index 0 to index 1, and ptr2 moves from index 3 to index 1. They meet after $a = 1$ round, at index 1. That is the expected output: the tail connects to node index 1.

6. Example 2 by hand

head = [1,2], pos = 0, so $a = 0$ and $L = 2$ . After round 1, slow is at index 1 and fast is at index 0. After round 2, both are at index 0, so $s = 2 = 1 \cdot L$ and $b = 0$ . In phase 2, ptr1 starts at head, index 0, and ptr2 starts at the meeting point, also index 0. The loop while ptr1 != ptr2 runs zero rounds, and the code returns index 0, the expected output. This matches $a = 0$ .

7. From the proof to the code

Proof	In `detectCycle`
both pointers start at `head`	`slow = fast = head`
after $s$ rounds, 1 step and 2 steps	`slow = slow.next` and `fast = fast.next.next`
the meeting, after $s = k \cdot L$ rounds	`if slow == fast:`
no cycle: `fast` reaches the end	`while fast and fast.next:` then `return None`
walk $a$ steps from `head` and from the meeting point	`ptr1 = head`, `ptr2 = slow`, then one step each per round
both arrive at the entrance together	`while ptr1 != ptr2:` then `return ptr1`

Phase 1 takes at most $a + L$ rounds and phase 2 takes $a$ rounds, so the code takes $O(n)$ time for a list of $n$ nodes. It keeps four pointers, so it uses $O(1)$ extra space and never changes the list.

Code Shape

Archetype Code Shape

Python

1	if not head or not head.next:
2	return None
3	slow = fast = head
4	has_cycle = False
5	while fast and fast.next:
6	slow = slow.next
7	fast = fast.next.next
8	if slow == fast:
9	has_cycle = True
10	break
11	if not has_cycle:
12	return None
13	ptr1 = head
14	ptr2 = slow
15	while ptr1 != ptr2:
16	ptr1 = ptr1.next
17	ptr2 = ptr2.next
18	return ptr1

Conceptual Narrative

Detecting a cycle is the first step; finding its exact entrance needs the second phase of Floyd's algorithm, which rests on the equation $L = k \cdot C - x$ .

🧭 Conceptual Foundation & Pattern Intuition

In Linked List Cycle I, we simply answered the binary question: does a cycle exist? We relied on the fact that within a cycle, a 2x runner gains 1 step per tick on a 1x runner, guaranteeing a collision. But knowing that a loop exists doesn't reveal where the straight track ends and the loop begins. Floyd's Phase 2 solves this without any extra memory ( $O(1)$ space) by exploiting an exact algebraic equivalence between the straightaway distance and the remaining loop distance.

🏟️ The Analogy: The Track with an Access Road

Imagine a running track shaped like the letter P or a lasso: a straight access road of length $L$ leads to a circular track of circumference $C$ . You and a friend start at the beginning of the road. Your friend runs twice as fast. When you both enter the circular track, your friend laps you and you collide at some point $x$ steps past the entry gate. If someone now places a runner at the very beginning of the access road and tells both runners to jog forward at exactly 1 step per tick, they will arrive at the entry gate at the exact same second! The distance from the start of the road to the gate equals the remaining distance around the loop back to the gate.

🔑 Why It Works

Let:

$L$ = distance from head to cycle entrance
$C$ = circumference (length) of the cycle
$x$ = distance from cycle entrance to the meeting point

When slow and fast collide:

slow traveled: $d_{slow} = L + x$
fast traveled: $d_{fast} = L + k \cdot C + x$ (where $k \ge 1$ is the number of full laps fast ran)
Since fast travels at double speed: $d_{fast} = 2 \cdot d_{slow}$ (or $2(L + x) = L + k \cdot C + x$ )
Simplifying: $2L + 2x = L + k \cdot C + x \implies$ $L = k \cdot C - x$

What does $k \cdot C - x$ mean? It is the exact remaining distance from the meeting point around the cycle back to the entrance gate! Therefore, walking $L$ steps from head and walking $L$ steps from the collision point (slow) brings both pointers to the cycle entrance simultaneously.

Advancing pointers at different speeds in Phase 2: In Phase 2, both p1 (from head) and p2 (from meeting point) must move at exactly 1 step per tick. Moving either at speed 2 skips the rendezvous point.
Returning boolean instead of node: LC 142 requires returning the ListNode object where the cycle begins, or None if no cycle exists.
Failing to return None on acyclic lists: If fast or fast.next reaches None, terminate and return None immediately before initiating Phase 2.
Floyd's Cycle Origin: pointer resets and phase 2 speed. In LC 142 (Linked List Cycle II), after the fast and slow pointers collide in Phase 1, you must reset ONE pointer to head and leave the other at the collision node, advancing both at 1 step per tick. Resetting both to head re-runs Phase 1 indefinitely; keeping fast at 2x speed causes them to overshoot and cycle past each other.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

"Return the node where the cycle begins" and a follow-up asking for O(1) memory: a list that may loop, and no room for a visited set. That is Fast & Slow Pointers, plus a second walk to find the entrance.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

fast has always taken twice as many steps as slow, so inside the cycle the gap closes by one per move and they must meet. From there, the cycle's first node is as far from the meeting point as from head, up to whole laps (L = k·C - d, derived in the invariant cards below).

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

while fast and fast.next: testing only fast crashes on fast.next.next for every list without a cycle that has an odd number of nodes.
if not has_cycle: return None before phase 2: when fast runs off the end there is no cycle, and phase 2 would walk into None.
Phase 2 moves ptr1 and ptr2 one step each: keeping ptr2 at two steps is not guaranteed to stop at the entrance.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"I'd use Fast & Slow Pointers in two phases. First slow moves one step and fast two; inside a cycle fast gains exactly one step per move, so it can't jump over slow and they meet. If fast runs off the end, there's no cycle and I return None. Then I start ptr1 at head and ptr2 at the meeting point and move both one step at a time: the cycle's first node is as far from the meeting point as from head, up to whole laps, so they meet exactly there. The trap is the loop test: while fast and fast.next, or fast.next.next crashes on a list without a cycle. It's O(N) time and O(1) extra space."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N)

Look at the execution steps: Phase 1 meets within at most C steps after slow enters loop (at most N steps). Phase 2 takes L steps to reach cycle origin. Total steps <= 2N = O(N).

SPACE COMPLEXITY

O(1) Auxiliary

Look at memory allocations: Call stack uses O(1) Iterative. Only stores two pointer references in O(1) auxiliary space.

Formal Recurrence Relation

$T(N) = Phase1 + Phase2 \le N + N = O(N)$

Derivation Progression

Phase 1 Collision

$T1 \le L + C \le N$

Fast pointer gains 1 node per step on slow inside the cycle.

Phase 2 Origin Rendezvous

$T2 = L \le N$

Both pointers move at 1 step per iteration across distance L.

Total Time Complexity

O(N) total steps

Strict linear runtime without modifying list nodes.

Variable Definitions

$N$

Total number of nodes in the linked list

$L$

Distance from head to cycle entrance

$C$

Circumference / length of the cycle

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative

🔵 Auxiliary Heap

O(1) Pointer references only

🟢 Output Space

O(1) Single node reference

Boundary Best / Worst Cases

Best Case

$O(1)$ only for 0 or 1 node; a list without a cycle still costs $O(N)$ (fast walks to the end, about $N/2$ steps).

Average Case

$O(N)$ .

Worst Case

$O(N)$ full traversal.

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "return the node where the cycle begins", "do not modify the linked list", "O(1) memory". A list that may loop and no room for a visited set: Fast & Slow Pointers, then a second walk from head to find the entrance.

CONSTRAINTS & BOUNDS

$0 \le N \le 10^4$ nodes. A visited set also runs in $O(N)$ time but stores up to $N$ node references; the follow-up asks for $O(1)$ memory, which only the two-speed walk gives.

FAANG PRODUCTION TRAPS & EDGE CASES

At scale: when each hop is expensive (following a redirect, a symlink or a reference stored on another machine), fast pays two hops per move, so phase 1 costs about three hops per step of slow; that is still far cheaper in memory than remembering every hop, which a long or endless chain can exhaust.

Core Algorithmic State Invariants

Why the Second Walk Stops at the Entrance

Let L be the distance from head to the cycle's first node, d the distance from there to the meeting point, and C the cycle length. At the meeting, fast has walked twice as far as slow, so 2(L + d) = L + d + k·C for some whole number of laps k, which gives L = k·C - d. From the meeting point, L steps are k·C - d steps: d short of k full laps, which is exactly the cycle's first node. So ptr1 from head and ptr2 from the meeting point, one step each, arrive there together after L steps.

Theory Context•Two Pointers & Sliding Window

MediumLC 142

Linked List Cycle II (LeetCode 142)

Target Frequency:AmazonMicrosoftGoogle

You're given the head of a linked list that may loop back on itself. Find and return the exact node where that loop begins — or null if the list has no loop at all.

(A test harness may describe the loop internally with a 0-indexed pos marking where the tail's next pointer reconnects, using -1 for no loop, but that index is never handed to your function.)

You must leave the linked list unmodified.

Worked Examples

Example 1

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

Output:tail connects to node index 1

Cyclic Linked List TopologyCycle at Node[1]

Floyd Cycle Detection

Access Road (L):1 node

Cycle Loop (C):3 nodes

Loop Entry:Node[1] (val: 2)

Collision / Meeting Point Detected!

Fast / Slow Pointer Invariant

Slow 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.

Cycle Origin Recovery ($L = kC - M$)

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.

Explanation: The tail node (-4) loops back into the node at index 1 (value 2), so that node is the cycle's entry point.

Example 2

Input:head = [1,2], pos = 0

Output:tail connects to node index 0

Explanation: The tail node (2) loops back into the node at index 0 (value 1), so that node is the cycle's entry point.

Example 3

Input:head = [1], pos = -1

Output:no cycle

Explanation: There is no cycle in the linked list.

⚖️Formal Constraints & Bounds

The number of the nodes in the list is in the range [0, 10⁴].
-10⁵ <= Node.val <= 10⁵
pos is -1 or a valid index in the linked-list.

Deep-Dive & Conceptual Insights

Core Insight

The distance from the head to the cycle origin equals the distance from the Phase 1 collision point to the cycle origin (L = k·C - x).

Real-World Scenario & Production Applications

Detecting circular dependencies in build systems, finding recurring loop states in state machines, and reference-counted garbage collection.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Phase 1 -- Fast & Slow Pointer Collision

Advance slow at 1x speed and fast at 2x speed until they collide inside the cycle loop, proving a cycle exists. If fast reaches null, terminate early.

Mathematical Recurrence / Code Invariant

slow, fast = head, head
while fast and fast.next:
    slow = slow.next; fast = fast.next.next
    if slow == fast: break
else: return None

Step-by-Step Execution Trace Table

Phase	Step	Ptr 1 Position	Ptr 2 Position	Distance / Action	Status
Phase 1: Rendezvous	1-3	`slow` at Node(-4)	`fast` at Node(-4)	Standard Floyd cycle detection	Rendezvous confirmed at Node(-4)
Phase 2: Origin Seek	Init	`p1 = head` (Node 3)	`p2 = meeting` (Node -4)	Reset one pointer to head; keep other at meeting node	Both step at uniform speed 1
Phase 2: Origin Seek	1	`p1 = p1.next` (Node 2)	`p2 = p2.next` (Node 2)	Step 1: `3 -> 2`; `-4 -> 2`	`p1 == p2`! Cycle entry is Node(2)

Worked on Paper

The Math, Step by Step

1. The distances in the list

Count distances in steps, where one step follows one next pointer. Name three numbers:

$a$ is the number of steps from head to the entrance, the first node of the cycle. This is the node the code must return.
$L$ is the cycle length, the number of nodes in the cycle. Walking $L$ steps inside the cycle brings you back to the same node.
$b$ is the number of steps from the entrance forward to the node where slow and fast meet, with $0 \le b < L$ .

The picture shows Example 1. The tail node $-4$ points back to the node with value 2 at index 1. So the entrance is index 1, $a = 1$ , and the cycle holds the three nodes 2, 0 and $-4$ , so $L = 3$ .

2. Where the two pointers are after $s$ rounds

Both pointers start at head. In every round of phase 1, slow moves 1 step and fast moves 2 steps. After $s$ rounds, slow has moved $s$ steps and fast has moved $2s$ steps.

3. Why phase 2 stops at the entrance

$s = k \cdot L \quad \text{for some whole number } k \ge 1$

slow stands $b$ steps past the entrance, so $s - a$ and $b$ differ by whole laps: $s - a = b + j \cdot L$ for some whole number $j \ge 0$ . Put $s = k \cdot L$ into this equation:

$a + b = (k - j) \cdot L$

4. Why phase 1 always ends, and the start at `head`

If the list has no cycle, fast reaches the end first. The loop while fast and fast.next stops, and the code returns None.

5. Example 1 by hand

head = [3,2,0,-4], pos = 1, so $a = 1$ and $L = 3$ . Nodes are named by index.

Round	`slow` moved	`slow` at	`fast` moved	`fast` at
1	1	index 1 (value 2)	2	index 2 (value 0)
2	2	index 2 (value 0)	4	index 1 (value 2)
3	3	index 3 (value $-4$ )	6	index 3 (value $-4$ )

6. Example 2 by hand

7. From the proof to the code

Proof	In `detectCycle`
both pointers start at `head`	`slow = fast = head`
after $s$ rounds, 1 step and 2 steps	`slow = slow.next` and `fast = fast.next.next`
the meeting, after $s = k \cdot L$ rounds	`if slow == fast:`
no cycle: `fast` reaches the end	`while fast and fast.next:` then `return None`
walk $a$ steps from `head` and from the meeting point	`ptr1 = head`, `ptr2 = slow`, then one step each per round
both arrive at the entrance together	`while ptr1 != ptr2:` then `return ptr1`

Code Shape

Archetype Code Shape

Python

1	if not head or not head.next:
2	return None
3	slow = fast = head
4	has_cycle = False
5	while fast and fast.next:
6	slow = slow.next
7	fast = fast.next.next
8	if slow == fast:
9	has_cycle = True
10	break
11	if not has_cycle:
12	return None
13	ptr1 = head
14	ptr2 = slow
15	while ptr1 != ptr2:
16	ptr1 = ptr1.next
17	ptr2 = ptr2.next
18	return ptr1

Conceptual Narrative

Detecting a cycle is the first step; finding its exact entrance needs the second phase of Floyd's algorithm, which rests on the equation $L = k \cdot C - x$ .

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: The Track with an Access Road

🔑 Why It Works

Let:

$L$ = distance from head to cycle entrance
$C$ = circumference (length) of the cycle
$x$ = distance from cycle entrance to the meeting point

When slow and fast collide:

slow traveled: $d_{slow} = L + x$
fast traveled: $d_{fast} = L + k \cdot C + x$ (where $k \ge 1$ is the number of full laps fast ran)
Since fast travels at double speed: $d_{fast} = 2 \cdot d_{slow}$ (or $2(L + x) = L + k \cdot C + x$ )
Simplifying: $2L + 2x = L + k \cdot C + x \implies$ $L = k \cdot C - x$

Advancing pointers at different speeds in Phase 2: In Phase 2, both p1 (from head) and p2 (from meeting point) must move at exactly 1 step per tick. Moving either at speed 2 skips the rendezvous point.
Returning boolean instead of node: LC 142 requires returning the ListNode object where the cycle begins, or None if no cycle exists.
Failing to return None on acyclic lists: If fast or fast.next reaches None, terminate and return None immediately before initiating Phase 2.
Floyd's Cycle Origin: pointer resets and phase 2 speed. In LC 142 (Linked List Cycle II), after the fast and slow pointers collide in Phase 1, you must reset ONE pointer to head and leave the other at the collision node, advancing both at 1 step per tick. Resetting both to head re-runs Phase 1 indefinitely; keeping fast at 2x speed causes them to overshoot and cycle past each other.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

while fast and fast.next: testing only fast crashes on fast.next.next for every list without a cycle that has an odd number of nodes.
if not has_cycle: return None before phase 2: when fast runs off the end there is no cycle, and phase 2 would walk into None.
Phase 2 moves ptr1 and ptr2 one step each: keeping ptr2 at two steps is not guaranteed to stop at the entrance.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"I'd use Fast & Slow Pointers in two phases. First slow moves one step and fast two; inside a cycle fast gains exactly one step per move, so it can't jump over slow and they meet. If fast runs off the end, there's no cycle and I return None. Then I start ptr1 at head and ptr2 at the meeting point and move both one step at a time: the cycle's first node is as far from the meeting point as from head, up to whole laps, so they meet exactly there. The trap is the loop test: while fast and fast.next, or fast.next.next crashes on a list without a cycle. It's O(N) time and O(1) extra space."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N)

Look at the execution steps: Phase 1 meets within at most C steps after slow enters loop (at most N steps). Phase 2 takes L steps to reach cycle origin. Total steps <= 2N = O(N).

SPACE COMPLEXITY

O(1) Auxiliary

Look at memory allocations: Call stack uses O(1) Iterative. Only stores two pointer references in O(1) auxiliary space.

Formal Recurrence Relation

$T(N) = Phase1 + Phase2 \le N + N = O(N)$

Derivation Progression

Phase 1 Collision

$T1 \le L + C \le N$

Fast pointer gains 1 node per step on slow inside the cycle.

Phase 2 Origin Rendezvous

$T2 = L \le N$

Both pointers move at 1 step per iteration across distance L.

Total Time Complexity

O(N) total steps

Strict linear runtime without modifying list nodes.

Variable Definitions

$N$

Total number of nodes in the linked list

$L$

Distance from head to cycle entrance

$C$

Circumference / length of the cycle

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative

🔵 Auxiliary Heap

O(1) Pointer references only

🟢 Output Space

O(1) Single node reference

Boundary Best / Worst Cases

Best Case

$O(1)$ only for 0 or 1 node; a list without a cycle still costs $O(N)$ (fast walks to the end, about $N/2$ steps).

Average Case

$O(N)$ .

Worst Case

$O(N)$ full traversal.

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

$0 \le N \le 10^4$ nodes. A visited set also runs in $O(N)$ time but stores up to $N$ node references; the follow-up asks for $O(1)$ memory, which only the two-speed walk gives.

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

Why the Second Walk Stops at the Entrance

Phase

Step

Ptr 1 Position

Ptr 2 Position

Distance / Action

Status

Phase 1: Rendezvous

1-3

slow at Node(-4)

fast at Node(-4)

Standard Floyd cycle detection

Rendezvous confirmed at Node(-4)

Phase 2: Origin Seek

Init

p1 = head (Node 3)

p2 = meeting (Node -4)

Reset one pointer to head; keep other at meeting node

Both step at uniform speed 1

Phase 2: Origin Seek

p1 = p1.next (Node 2)

p2 = p2.next (Node 2)

Step 1: 3 -> 2; -4 -> 2

p1 == p2! Cycle entry is Node(2)

Round

slow moved

slow at

fast moved

fast at

index 1 (value 2)

index 2 (value 0)

index 1 (value 2)

index 3 (value

-4

)

index 3 (value

-4

)

Proof

In detectCycle

both pointers start at head

slow = fast = head

after

s

rounds, 1 step and 2 steps

slow = slow.next and fast = fast.next.next

the meeting, after

s = k \cdot L

rounds

if slow == fast:

no cycle: fast reaches the end

while fast and fast.next: then return None

walk

a

steps from head and from the meeting point

ptr1 = head, ptr2 = slow, then one step each per round

both arrive at the entrance together

while ptr1 != ptr2: then return ptr1

Phase

Step

Ptr 1 Position

Ptr 2 Position

Distance / Action

Status

Phase 1: Rendezvous

1-3

slow at Node(-4)

fast at Node(-4)

Standard Floyd cycle detection

Rendezvous confirmed at Node(-4)

Phase 2: Origin Seek

Init

p1 = head (Node 3)

p2 = meeting (Node -4)

Reset one pointer to head; keep other at meeting node

Both step at uniform speed 1

Phase 2: Origin Seek

p1 = p1.next (Node 2)

p2 = p2.next (Node 2)

Step 1: 3 -> 2; -4 -> 2

p1 == p2! Cycle entry is Node(2)

Round

slow moved

slow at

fast moved

fast at

index 1 (value 2)

index 2 (value 0)

index 1 (value 2)

index 3 (value

-4

)

index 3 (value

-4

)

Proof

In detectCycle

both pointers start at head

slow = fast = head

after

s

rounds, 1 step and 2 steps

slow = slow.next and fast = fast.next.next

the meeting, after

s = k \cdot L

rounds

if slow == fast:

no cycle: fast reaches the end

while fast and fast.next: then return None

walk

a

steps from head and from the meeting point

ptr1 = head, ptr2 = slow, then one step each per round

both arrive at the entrance together

while ptr1 != ptr2: then return ptr1

Detecting a cycle is the first step; finding its exact entrance needs the second phase of Floyd's algorithm, which rests on the equation $L = k \cdot C - x$ .

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: The Track with an Access Road

🔑 Why It Works

Let:

$L$ = distance from head to cycle entrance
$C$ = circumference (length) of the cycle
$x$ = distance from cycle entrance to the meeting point

When slow and fast collide:

slow traveled: $d_{slow} = L + x$
fast traveled: $d_{fast} = L + k \cdot C + x$ (where $k \ge 1$ is the number of full laps fast ran)
Since fast travels at double speed: $d_{fast} = 2 \cdot d_{slow}$ (or $2(L + x) = L + k \cdot C + x$ )
Simplifying: $2L + 2x = L + k \cdot C + x \implies$ $L = k \cdot C - x$

Linked List Cycle II (LeetCode 142)

Worked Examples

⚖️Formal Constraints & Bounds

Core Insight

Real-World Scenario & Production Applications

Subproblems & Recurrence Decomposition3 Phases

Step-by-Step Execution Trace Table

The Math, Step by Step

1. The distances in the list

2. Where the two pointers are after sss rounds

3. Why phase 2 stops at the entrance

4. Why phase 1 always ends, and the start at head

5. Example 1 by hand

6. Example 2 by hand

7. From the proof to the code

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: The Track with an Access Road

🔑 Why It Works

4-Phase Thought Process Model

Pattern Recognition Signals

Formulating the Predicate & Invariants

Silent Failure Traps & Edge Cases

The 60-Second Interview Pitch

Complexity & Mathematical Proof

Derivation Progression

Variable Definitions

Memory Architecture & Bounds

Boundary Best / Worst Cases

Senior SWE Deconstruction & Hardware Caveats

Core Algorithmic State Invariants

Linked List Cycle II (LeetCode 142)

Worked Examples

⚖️Formal Constraints & Bounds

Core Insight

Real-World Scenario & Production Applications

Subproblems & Recurrence Decomposition3 Phases

Step-by-Step Execution Trace Table

The Math, Step by Step

1. The distances in the list

2. Where the two pointers are after sss rounds

3. Why phase 2 stops at the entrance

4. Why phase 1 always ends, and the start at head

5. Example 1 by hand

6. Example 2 by hand

7. From the proof to the code

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: The Track with an Access Road

🔑 Why It Works

4-Phase Thought Process Model

Pattern Recognition Signals

Formulating the Predicate & Invariants

Silent Failure Traps & Edge Cases

The 60-Second Interview Pitch

Complexity & Mathematical Proof

Derivation Progression

Variable Definitions

Memory Architecture & Bounds

Boundary Best / Worst Cases

Senior SWE Deconstruction & Hardware Caveats

Core Algorithmic State Invariants

Linked List Cycle II (LeetCode 142)

Worked Examples

⚖️Formal Constraints & Bounds

Core Insight

Real-World Scenario & Production Applications

Subproblems & Recurrence Decomposition3 Phases

Step-by-Step Execution Trace Table

The Math, Step by Step

1. The distances in the list

2. Where the two pointers are after sss rounds

3. Why phase 2 stops at the entrance

4. Why phase 1 always ends, and the start at head

5. Example 1 by hand

6. Example 2 by hand

7. From the proof to the code

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: The Track with an Access Road

2. Where the two pointers are after $s$ rounds

4. Why phase 1 always ends, and the start at `head`

2. Where the two pointers are after $s$ rounds

4. Why phase 1 always ends, and the start at `head`

2. Where the two pointers are after $s$ rounds

4. Why phase 1 always ends, and the start at `head`

2. Where the two pointers are after $s$ rounds

4. Why phase 1 always ends, and the start at `head`