The problem
If a linked list has a cycle, return the node where the cycle begins; otherwise return none.
Input: 3 → 2 → 0 → −4 → 7, last links back to position 1 Output: position 1
Picture it
Picture the tortoise and hare on a looping track. After they meet inside the loop, put the tortoise back at the start. Now both walk one step at a time; the point where they meet again is exactly where the loop begins (a neat consequence of the distances involved).
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Floyd’s algorithm, phase two: reset one pointer to head and walk both at speed 1.
Python solution
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow, fast = slow.next, fast.next
return slow
return NoneIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.