Floyd's Tortoise and Hare Algorithm | 142) Linked List Cycle II | Fast and Slow Pointer

Hey everyone!

I recently solved the problem "Linked List Cycle II" and wanted to share my approach. The problem asks to detect if a linked list has a cycle and return the node where the cycle begins.

To solve this problem, we can use the "Floyd's Tortoise and Hare" algorithm, which involves using two pointers: a slow pointer and a fast pointer. We start both pointers at the head of the linked list and move them through the list one node at a time. The slow pointer moves forward one node at a time, while the fast pointer moves forward two nodes at a time.

If there is a cycle in the linked list, the fast pointer will eventually "lap" the slow pointer, and they will meet at a common node. At this point, we know that the linked list has a cycle.

To find the starting node of the cycle, we can use the fact that the distance traveled by the slow pointer from the head of the linked list to the starting node of the cycle is the same as the distance traveled by the fast pointer from the meeting point to the starting node of the cycle. Therefore, we can move one of the pointers back to the head of the linked list and then move both pointers forward one node at a time until they meet at the starting node of the cycle.

Check this for Detailed Solution : https://leetcode.com/problems/linked-list-cycle-ii/solutions/3276306/beats-100-0ms-fast-and-slow-pointer-java-python3-detailed-explanation/

Feel free to add more, Thank You!

Comments (1)