142. Linked List Cycle II

寻找有环链表环的起点。

假设头节点距离环的起点距离为a, 起点距离第一次相遇点为b, 环长L
则有a+b+kL = 2(a+b),即a+b=kL

由于a=kL-b, 让两个指针分别从相遇点和头节点处出发，则二者会在环的起点处相遇。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return None
        fast = head
        slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                break
        if fast.next is None or fast.next.next is None:
            return None
        
        slow = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast