Linked List Cycle

Given the head of a linked list, determine if the linked list has a cycle in it. A cycle occurs if a node in the list can be reached again by continuously following the next pointer.

We can iterate through the list and store each node we visit in a Hash Set. Before visiting a node, we check if it's already in the set. If it is, we found a cycle. If we reach null, there is no cycle.

• Drawback: This uses O(N) extra space to store references to all nodes.

Using O(N) space is acceptable, but can we do better? Can we detect a cycle using only O(1) space without modifying the list structure?

Imagine two runners on a circular track. One is fast (Hare) and one is slow (Tortoise). If there is a loop, the Fast runner will eventually lap the Slow runner and they will meet explicitly inside the loop. If there is no loop, the Fast runner will just finish the race (reach null) first.

Watch the 'Tortoise and Hare' race. See how the Fast pointer catches the Slow pointer.