Algorithms

The Two-Pointer Derivation That Finds a Linked List Cycle's Entry in O(1) Space

By 小月土星 · Aug 6, 2026

Read original on juejin.cn ↗ Google Translate ↗ Alt translation

Cycle detection is a staple of linked-list interviews, but many candidates can only detect the loop — not pinpoint its entry. Knowing the two-phase pointer reset and the math behind it turns a memorized trick into a derivable solution, which is what interviewers actually probe for.

Summary

LeetCode 142 asks for the first node of a cycle, not just a boolean. The fast-slow pointer approach solves it in O(n) time and O(1) space by exploiting a distance invariant: the head-to-entry gap equals the collision-point-to-entry gap modulo the cycle length. After the initial meeting inside the loop, placing one pointer back at the head and stepping both one node at a time guarantees they converge at the entry.

A walkthrough of the math shows why the relationship holds — fast covers twice the distance of slow, and the algebra reduces to a = k(b+c) - b, which simplifies to the head-to-entry distance matching the remaining arc from the collision point. The post also flags a readability win: using a fresh `start` variable for the second phase instead of reusing `slow` keeps the chasing and locating responsibilities separate, which reads cleaner in an interview setting.

Edge cases like a single-node list or a self-loop are handled by a standard initialization (`slow = head, fast = head`) and a null-check on `fast` and `fast.next` inside the loop. The final code is a compact, interview-ready JavaScript implementation that avoids the O(n) memory cost of a hash-set approach.

Takeaways

— After the fast and slow pointers first meet inside the cycle, resetting one pointer to the head and advancing both at one step per iteration makes them collide exactly at the cycle's entry node.

— The invariant comes from the distance equation: 2(a+b) = a + b + k(b+c) simplifies to a = k(b+c) - b, meaning the head-to-entry gap equals the collision-point-to-entry gap modulo the cycle length.

— Using a dedicated `start` variable for the second traversal instead of reusing `slow` separates the chase phase from the locate phase, improving readability without changing the logic.

— Standard initialization (`slow = head, fast = head`) handles self-loop edge cases correctly; the variant that starts one step ahead works for this problem but is less general.

— Checking `fast && fast.next` in the loop condition is sufficient to detect a null-terminated list — only the fast pointer can reach the end first.

— A hash-set solution costs O(n) space; the two-pointer method keeps space at O(1), which is the expected optimal answer in most interviews.

Conclusions

The post's emphasis on variable hygiene — introducing a fresh `start` pointer — addresses a real interview pitfall: reusing `slow` muddies the two distinct phases of the algorithm and makes the code harder to explain under pressure.

Many online solutions skip the derivation and just present the two-pointer reset as a recipe. Walking through the algebra step by step turns the algorithm from a magic incantation into a provable property of distances on a circle, which is what separates a passing answer from a strong one.

The note that the 'start one step ahead' initialization works but isn't universally safe is a subtle correctness point — self-loops or very short cycles can break non-standard initializations, and interviewers often test those edges.

Concepts & terms

Floyd's cycle detection (tortoise and hare)

A two-pointer algorithm where a slow pointer moves one step and a fast pointer moves two steps per iteration. If a cycle exists, the pointers will meet inside it; if not, the fast pointer reaches null. After meeting, resetting one pointer to the head and moving both at the same speed locates the cycle's entry node.

Cycle entry invariant

The mathematical relationship a = k(b+c) - b, where a is the distance from head to cycle entry, b is the distance from entry to the meeting point, and c is the remaining arc back to the entry. It implies that the distance from the head to the entry equals the distance from the meeting point to the entry, modulo the cycle length.

Source: juejin.cn ↗ Google Translate ↗ Backup ↗