The problem
Return the node where a linked list’s cycle begins, or null if there is no cycle. Use O(1) memory.
Stuck? Reveal hints one at a time
How to approach it
- 1Advance slow by 1 and fast by 2 until they meet (cycle) or fast hits null (no cycle).
- 2On meeting, move slow back to head, keep fast at the meeting point.
- 3Advance both one step at a time; the node where they meet is the cycle entrance.
Key insight
Math behind phase two: if head→entrance = a and entrance→meeting = b, the meeting happens a steps short of a full loop — so a steps from head and a steps from the meeting point land on the same node.
The solution
Watch out for
- Compare NODES (identity), not values — duplicated values are legal.
- The meeting point is generally NOT the cycle start; phase two is mandatory.