Medium Slow/Fast + Reset Linked Lists
In plain English: Find exactly which node a linked list starts looping at.
After the pointers meet inside the cycle, the distance from head to cycle start equals the distance from the meeting point to cycle start — a property of Floyd's algorithm.
Prompt
Find the node where the cycle begins in a linked list.
Try to write it from scratch before scrolling down.
Solution
def cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
# equal distance to cycle start
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None