Detect Cycle in a Linked List

To detect a cycle efficiently, I would avoid using a hash set to track visited nodes, as that consumes O(n) extra space. Instead, I recommend Floyd's Tortoise and Hare algorithm, which achieves O(1) space complexity. Here is how I would implement it: Initialize two pointers, 'slow' and 'fast', both starting at the head. The slow pointer moves one node forward per iteration, while the fast pointer moves two nodes forward. If there is no cycle, the fast pointer will eventually reach the end of the list (null). However, if a cycle exists, the fast pointer will eventually enter the loop and catch up to the slow pointer from behind, causing them to meet at some node within the cycle. For example, consider a list where the tail connects back to the third node. The fast pointer loops around faster than the slow one, guaranteeing a collision inside the loop. Once they meet, we return true. If the fast pointer hits null, we return false. This approach is robust because it handles all edge cases, including single-node cycles, without requiring additional data structures, aligning perfectly with the performance standards expected at Microsoft.