Skip to main content

142. Linked List Cycle II

class Solution:
def detectCycle(self, head):
'''
.___a___.___C-b___.
(_________) -> C: cycle
b

slow: a+C-b + xC
fast: a+C-b + yC

2 slow = fast
=> a+C-b = (y-2x)C
=> a = (y-2x-1)C+b

.___(y-2x-1)C+b___.___C-b___.
(_________)
b

=> a mod C = b mod C
'''
l = r = head
while r and r.next:
l, r = l.next, r.next.next
if l is r:
break
else:
return

while head is not r:
head, r = head.next, r.next
return head