题解 | #链表中环的入口结点#

当链表有环时，获取脸变环的位置的方法： 1.先按有无环的判断流程，当快慢指针不相遇，则直接返回空 2.当快慢指针相遇时，快指针回到起点，慢指针呆在原地，快慢指针以相同的速度前进，下一次相遇的地点即为环的入口位置

推导过程：

x:链表中无环的长度 y:相遇点离环初始位置的距离 z:环剩下的距离

当快慢指针相遇时：

快指针运行了： x + n(y + z) + y

慢指针运行了： x + m(y + z) + y

m,n为整数

由于快指针是慢指针的两倍，有：

x + n(y + z) + y = 2 ( x + m(y + z) + y)

进一步求得：

x + y = (n -2m)(y + z)

其中，y + z 即为环的长度

此时快指针回到起点，慢指针呆在原地，假设快指针相遇时离初始位置S，当快慢指针以相同速度继续遍历，当再次相遇时，存在以下关系：

S + a(y + z) = b(y + z) - y

a,b亦为整数，当b=n、a=2m时，即为上式的结果，此时S = x, 即快慢指针再次相遇时正好处在环初始节点位置。

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead == None:
            return None

        fast = pHead
        slow = pHead
        is_ring = False
        while fast is not None and fast.next is not None:
            fast = fast.next.next 
            slow = slow.next 
            if fast == slow:
                is_ring = True
                fast = pHead
                break
        if is_ring:
            while fast != slow:
                fast = fast.next 
                slow = slow.next
            return fast 
        else: 
            return None