Linked List Cycle II

Statement

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. Solve in O(1) extra memory.

Examples

head = 3 → 2 → 0 → -4 → 2 (back to index 1)
→ node with value 2 (index 1) - the cycle's entry

head = 1 → 2 → 1 (back to index 0)
→ node with value 1 (index 0)

head = 1 → null
→ null

head = 1 → 2 → null
→ null

Constraints

• 0 ≤ list length ≤ 10⁴
• -10⁵ ≤ Node.val ≤ 10⁵
• pos (the cycle's entry index) is -1 if no cycle, otherwise 0 ≤ pos < length.
• Solve in O(1) extra memory. The hash-set version is too easy; the interview is testing whether you know Floyd's.

What this problem is really testing

Three things at once: (1) detecting a cycle with two pointers at different speeds; (2) understanding the modular-arithmetic identity that lets you locate the cycle's entry without traversing the cycle's length; (3) implementing both phases without losing your null guards. The hash-set solution exists but is explicitly cheap; the O(1)-memory constraint is what makes the problem worth asking.