Medium Slow/Fast Linked Lists
In plain English: Figure out if a linked list loops back on itself instead of ending at null.
If there's a cycle, a fast pointer (2x speed) will eventually lap the slow pointer — like two runners on a circular track.
Prompt
Detect if a linked list has a cycle using O(1) space.
Try to write it from scratch before scrolling down.
Solution
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# fast laps slow if cycle exists
if slow == fast:
return True
return False