If the list has a cycle, return the node where the cycle begins. Otherwise return null, using O of 1 extra space.
DSA Animator › DSA Revision › Linked List › Linked List Cycle II
Remember: the head and the meeting point are the same distance from the entry. Meet, reset one pointer, then walk together. The video solves Linked List Cycle II (LeetCode 142, Medium) with the Fast & Slow Pointers pattern from the Linked List topic, and you can replay every step in the interactive Linked List Cycle II animation.
If the list has a cycle, return the node where the cycle begins. Otherwise return null, using O of 1 extra space.
For 3, 2, 0, minus 4, where the last node points back to 2, the cycle starts at 2.
A hash set returns the first node seen twice, but uses O of n space. Floyd's algorithm can find the entry too.
First, run slow and fast until they meet inside the cycle. Then move one pointer back to the head. Move both one step at a time, and they meet exactly at the cycle entry.
As in problem 141, slow and fast meet at minus 4. Put one pointer back at the head, 3. Step both once: the head pointer moves to 2, and the other goes from minus 4 to 2. They meet at 2, which is the entry of the cycle.
In code, the first loop is the cycle check from problem 141. After they meet, set a pointer to head. Move both one step until they are equal, and return that node, so it's O of n time and O of 1 space.
Remember: the head and the meeting point are the same distance from the entry. Meet, reset one pointer, then walk together.