TWO RUNNERS START AT THE HEAD. SLOW HOPS ONE NODE, FAST HOPS TWO. IF THE CHAIN LOOPS, FAST LAPS THE TRACK AND CATCHES SLOW FROM BEHIND. IF IT ENDS, FAST RUNS OFF THE TAIL. LANDING ON THE SAME NODE MEANS A CYCLE.
ON A LOOP A FAST RUNNER ALWAYS CATCHES A SLOW ONE. FAST GAINS ONE NODE EACH STEP, SO THE GAP SHRINKS TO ZERO. NO LOOP MEANS FAST REACHES THE END AND STOPS.
BLUE SLOW HOPS ONE, GREEN FAST HOPS TWO. WATCH THE GAP CLOSE. THE GOLD TILE IS WHERE THEY MEET, PROVING THE CYCLE.
1def hasCycle(head):2 fast, slow = head, head3 while fast and fast.next:4 fast = fast.next.next5 slow = slow.next6 if slow == fast:7 return True8 return False
FAST GAINS ONE NODE ON SLOW EACH STEP, SO THEY MEET WITHIN N STEPS.
JUST TWO POINTERS, SLOW AND FAST. NOTHING IS REMEMBERED.