python leetcode 142. Linked List Cycle II

まずリングかどうかを判断します.リング長をLとし,リングの長さMではなく,リング中のNで出会う.それではfastはM+K 1 L+N、slowはM+K 2 L+Nを歩きました.fast=2slow,M+K1L+N=2*(M+K2*L+N),N=(K1-K2)*L-M.NからMを歩くとループの始点に着くのが見えます.

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next ==None:
            return None 
        fast = head 
        slow = head 
        while fast and fast.next:
            
            fast = fast.next.next 
            slow = slow.next 
            if fast == slow:
                break 
        if fast == slow:
            slow = head 
            while slow != fast:
                slow = slow.next 
                fast = fast.next 
            return slow 
        return None