Detect Loop in Linked List
A cycle in a linked list occurs when a node's next pointer points back to a previously visited node rather than to null or a new node. Cycles are typically...
Finding Cycles in Linked Lists Using Floyd's Tortoise and Hare
A cycle in a linked list occurs when a node's next pointer points back to a previously visited node rather than to null or a new node. Cycles are typically bugs caused by incorrect pointer manipulation during insertion or deletion. Detecting them is important for preventing infinite loops during traversal.
Floyd's cycle detection algorithm, also known as the tortoise and hare algorithm, detects cycles in O(n) time and O(1) space. Use two pointers: a slow pointer that advances one step at a time and a fast pointer that advances two steps at a time. If there is no cycle, the fast pointer reaches null. If there is a cycle, the fast pointer laps the slow pointer: both end up inside the cycle, and eventually they occupy the same node.
Proof of correctness: suppose the cycle has length c and starts at some position k in the list. Once both pointers enter the cycle, the fast pointer gains one position on the slow pointer per iteration. Starting from some point where they are separated by d positions within the cycle, after d iterations the fast pointer will have lapped the slow pointer and they meet. The total number of steps until meeting is at most O(n).
Finding the start of the cycle is a follow-up that uses an elegant mathematical property. After the fast and slow pointers meet inside the cycle, reset one pointer to the head while leaving the other at the meeting point. Advance both pointers one step at a time. They will meet exactly at the cycle's start node. This works because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start within the cycle (modular arithmetic within the cycle length).
An alternative approach uses a hash set to track visited nodes. As you traverse the list, check each node against the set. If it is already in the set, the current node is the start of the cycle. This approach is O(n) time and O(n) space, less efficient in memory but easier to understand and implement correctly.
Removing the cycle once found: after identifying the cycle start node using Floyd's method, traverse the list again to find the node whose next pointer is the cycle start. Set that node's next to null to break the cycle.
Worked example: list with nodes 1 -> 2 -> 3 -> 4 -> 5 -> 3 (pointing back to node 3, creating a cycle). Floyd's: slow and fast both start at 1. After steps: slow at 2/3/4/5/3, fast at 3/5/4/3/5. They meet at node 5 (or wherever the offset places them). Resetting slow to head: both advance one step at a time, meeting at node 3, the cycle start.
Interview tip: know both the hash set approach and Floyd's algorithm. Mention Floyd's algorithm and state its O(1) space advantage. If asked to also find the start of the cycle, walk through the mathematical reasoning before implementing.