链表中环的入口结点

问题简述

给一个长度为 n 的链表，若其中包含环，请找出该链表的环的入口结点，否则返回null。

链表中环的入口结点_牛客题霸_牛客网

思路：快慢指针

• 快指针 fast 每次走两步，慢指针 slow 每次走一步；

• 若存在环，则 fast 与 slow 必会相遇；

• 相遇后，将 slow 重新指向 pHead，然后，双指针正常每次走一步；

• 当再次相遇时，即为入口节点；

• 注意无环的情况；

证明：

• 假设存在环，记环之前的节点数即为 $a$（不包括入口节点），环的节点数为 $b$；当 fast 和 slow 相遇时距离环入口的步数为 $c$；

• 下面证明：$a=c$

• 记 fast 和 slow 走的步数分别为 $f$ 和 $s$，且 $f-s = nb$，即 fast 比 slow 多走了 n 圈；又 $f=2s$，可得 $s=nb$，而实际上 slow 走的距离 $s=a + (n-1)b + (b-c)$，联立得 $a=c$；

• 因此当 fast 和 slow 在环内相遇时，将 slow 重新指向 pHead，然后双指针再次相遇时即为入口节点（每次走一步）；

Python

class Solution:
    def EntryNodeOfLoop(self, pHead: ListNode):
        # write code here

        no_cycle = True
        slow = fast = pHead
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                no_cycle = False
                break

        if no_cycle:
            return None

        slow = pHead
        while slow != fast:
            slow = slow.next
            fast = fast.next

        return slow