Leetcode 142. 环形链表 II Linked List Cycle II - Python 双指针法

# 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:
        fast, slow = head, head
        #让快慢指针一快一慢 快的追慢的 直至相遇
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
#相遇时 用q记下此时相遇的节点位置 用p从首元节点开始跑
                p = head
                q = slow
                while p != q:
#当二者相遇时，p和q所指的节点就是环的入口
                    p = p.next
                    q = q.next
                return p
        return None

该算法由数学计算可推导出： x = (n-1)(Y+Z) + Z

其中

x：首元节点到环入口的节点个数；

n：快指针在环内循环的圈数；

Y：环入口到快慢指针相遇点之间的节点个数：

Z：环中快慢指针相遇点到环入口之间的节点个数

关于为什么慢指针在环内循环不到一圈就能被快指针追上：

1.快指针肯定先于慢指针入环。

2.当慢指针入环时，快指针可在环中任意位置。

3.此时slow与fast之间的距离（从slow沿顺时针方向数到fast）记为i，环周长记为c。

4.fast追上slow（沿顺时针方向追）需要c-i次跳动，即slow移动c-i次被追上。

5.因为i>0 ， 所以c-i < c  i.e. slow在一圈内就会被fast追上。