Edit Problem

Title

Problem URL

Difficulty

Tags

Fast & Slow Pointers

Go file path (optional)

Notes (optional)

## What It Does

This function returns the actual node where a cycle begins in a linked list — not just whether one exists. It does this in three distinct phases:

1. **Detect the cycle** — standard Floyd's tortoise-and-hare. `slow` and `fast` meet somewhere inside the cycle (not necessarily at the start).
2. **Measure the cycle length** — starting from the intersection point, `intersection` laps itself one full time, counting the steps. This gives the exact number of nodes in the cycle.
3. **Find the start** — `ahead` gets a head start of exactly `cycleLength` steps over `behind`. Then both advance one step at a time. When they meet, that node is the cycle entry — because `ahead` is always exactly one full cycle ahead, so they converge precisely at the start.

For example, `1 → 2 → 3 → 4 → 5 → 3 (cycle)`: Floyd's meets somewhere in `3 → 4 → 5`, cycle length is measured as `3`, `ahead` gets a 3-node head start, and both pointers converge at node `3` — the cycle entry.

---

## Complexity Analysis

**Time Complexity: O(n)**
Phase 1 takes O(n) to detect the cycle. Phase 2 takes O(k) where k is the cycle length (k ≤ n). Phase 3 takes O(n) for the two-pointer convergence. All three phases are linear — O(n) overall.

**Space Complexity: O(1)**
A handful of pointer variables. No sets, no visited tracking, no auxiliary storage.

---

## A Few Notes

**This is a less common but more explicit alternative to the classic reset trick.** The textbook approach after Floyd's meeting point is: reset `slow` to `head`, advance both `slow` and `fast` one step at a time, and they'll meet at the cycle start. That works because of a mathematical property of the meeting point. This solution instead *measures* the cycle length explicitly and uses the fixed-gap two-pointer technique — more code, but the reasoning is easier to follow and explain without needing to prove the math.

**The cycle length measurement loop has the same `break`-on-nil risk pattern** as the palindrome reversal — it assumes a cycle was actually found before entering. If `fast` exited the first loop because `fast == nil` (no cycle), `intersection` would be `nil` and `intersection.Next` would panic. A guard checking whether `slow == fast` after the first loop before entering phase 2 would make this production-safe.

**This is the natural culmination of the cycle detection problem from earlier.** `linked_list_cycle` told you *if* there's a cycle. This tells you *where* it starts — same primitive, one layer deeper. The pattern of building on prior solutions continues.

First solved

May 28, 2026