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

方法一 ：用列表，当节点重复存在于列表时，则说明是环的入口

方法二：快慢指针 第一次相遇时，其中一指针保持在原来的地方，另一指针回头部，同时逐步遍历，再次相遇的地方就是环的入口

# 找到链表中的环的入口
    def EntryNodeOfLoop(self, pHead : ListNode):
        # write code here
        # 方法一 ：用列表，当节点重复存在于列表时，则说明是环的入口
        ls = []
        while pHead:
            if ls.__contains__(pHead):
                return pHead
            ls.append(pHead)
            if pHead.next:
                pHead = pHead.next
            else:
                return None
        return None

        # 方法二：快慢指针 第一次相遇时，其中一指针保持在原来的地方，另一指针回头部，同时逐步遍历，再次相遇的地方就是环的入口
        sNode = self.hasCycle(pHead)
        if sNode == None:
            return None

        fNode = pHead
        while fNode != sNode:
            fNode = fNode.next
            sNode = sNode.next
        return fNode
    
    def hasCycle(self, pHead : ListNode):
        if not pHead:
            return None
        fNode = pHead
        sNode = pHead
        while fNode and fNode.next:
            fNode = fNode.next.next
            sNode = sNode.next
            if fNode == sNode:
                fNode = pHead
                return sNode
        return None