Given the head of a linked list, decide whether it has a cycle. A cycle means some node can be reached again by following next pointers.
DSA Animator › DSA Revision › Linked List › Linked List Cycle
Remember: Floyd's tortoise and hare. A faster runner on a circular track always catches the slower one. The video solves Linked List Cycle (LeetCode 141, Easy) with the Fast & Slow Pointers pattern from the Linked List topic, and you can replay every step in the interactive Linked List Cycle animation.
Given the head of a linked list, decide whether it has a cycle. A cycle means some node can be reached again by following next pointers.
For 3, 2, 0, minus 4, where the last node points back to 2, the answer is true.
Storing every visited node in a hash set works, but uses O of n space. Two pointers can do it with O of 1 space.
Move a slow pointer one step and a fast pointer two steps at a time. If there is no cycle, fast reaches null. If there is a cycle, fast laps around and meets slow.
Both start at 3. Slow moves to 2, and fast moves to 0. Slow moves to 0, and fast goes around the loop to 2. Slow moves to minus 4, and fast also lands on minus 4. They met, so there is a cycle.
In code, loop while fast and fast dot next are not null. Move slow one step and fast two steps. If they are the same node, return true, otherwise return false after the loop, so it's O of n time and O of 1 space.
Remember: Floyd's tortoise and hare. A faster runner on a circular track always catches the slower one.