142. Linked List Cycle II - LeetCode

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