链表中环的入口节点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路

首先是判断链表中是否有环，这里使用双指针，分成快慢两个指针。如果有环的话，指针进入环内就会变成追赶问题。先进环的快指针一定会追上慢指针。
当两个指针追赶上之后。
判定有环之后，在开头重新再定义一个指针，这个指针每次走一步，慢指针在相遇的位置开始行动，每次也走一步，两个指针一定会相遇，而且相遇点就是入口。 这里可以通过数学的方法证明这个相遇点就是入口。个人懒就没有具体证明。

代码

def EntryNodeOfLoop(self, pHead):
        if pHead is None:
            return None
        slowNode = pHead
        quickNode = pHead
        while quickNode is not None and quickNode.next is not None:
            slowNode = slowNode.next
            quickNode = quickNode.next.next
            if slowNode == quickNode: #两个点相遇，证明有环
                catchNode = pHead #在表头建第三个指针，一定会和慢指针在入口相遇
                while catchNode != slowNode:
                    catchNode = catchNode.next
                    slowNode = slowNode.next
                return catchNode
        return None #while循环结束，无环链表