After a cycle is detected, how can you find the start node of the cycle?

• A. Move the slow pointer to the head and continue until meeting the fast pointer.
• B. Restart the fast pointer from the head and move both pointers; they meet at the start.
• C. Move the slow pointer to the head and move both pointers at the same speed until they meet; the meeting point is the cycle start.
• D. Reset one pointer to head and move both pointers at the same speed until they meet; the meeting point is the cycle start.

Answer: (D)

When the two pointers have met inside the cycle, you can locate the cycle’s start by resetting one pointer to the head and then moving both pointers one step at a time. They will meet at the node where the cycle begins. Intuition: let μ be the distance from head to the cycle start, and λ be the cycle length. At the meeting, the slow pointer has traveled μ + x (where x is how far into the cycle they met), and the fast pointer has traveled μ + x plus a multiple of λ. This forces μ + x to be a multiple of λ. Now, moving one pointer back to head and advancing both pointers at the same speed means after μ steps, the pointer from head arrives at the cycle start, while the pointer from the meeting point has moved μ steps along the cycle to also reach the cycle start. They meet there, which is exactly the start of the cycle. This is the standard method for finding the cycle entry.