BM7 链表中环的入口结点

题目描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
输入描述：
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
返回值描述：
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
连接：https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=295&tqId=23449&ru=%2Fpractice%2F65cfde9e5b9b4cf2b6bafa5f3ef33fa6&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj

解题思路

首先复习一下普通的检测环

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head is None:
            return False
        slow, fast = head, head.next
        while fast is not None and fast.next is not None:
        # 如果没有fast.next is not None，fast.next为None的话会运行出错
            if slow == fast:
                return True
            slow = slow.next
            fast = fast.next.next
        return False

在此将快慢指针的起始位置都改为head，则检测环的代码改成

def MeetPosition(self, pHead):
        if not pHead or not pHead.next:
            return None
        n1, n2 = pHead, pHead
        startFlag = 0
        while n2 and n2.next:
            if n1 == n2 and startFlag: # 只有开始启动之后的相等才算数
                return n1
            startFlag = 1
            n1 = n1.next
            n2 = n2.next.next
        return None

用这种方式的好处是，可以用数学证明，接下来如果：

快指针从上述代码的相遇点开始每次走一步，慢指针从起点开始每次走一步，那么这两个指针的相遇点正好是环的入口结点。

以此可以正式编写代码

解题代码

class Solution:
    def MeetPosition(self, pHead):
        if not pHead or not pHead.next:
            return None
        n1, n2 = pHead, pHead
        startFlag = 0
        while n2 and n2.next:
            if n1 == n2 and startFlag: # 只有开始启动之后的相等才算数
                return n1
            startFlag = 1
            n1 = n1.next
            n2 = n2.next.next
        return None

    def EntryNodeOfLoop(self, pHead):
        m = self.MeetPosition(pHead)
        if not m:
            return None
        n = pHead
        while m != n:
            m = m.next
            n = n.next
        return m