1，快慢指针解决

在前面我们提到过快慢指针，判断是否有环。如果有环，在来找环的入口。如果没环直接返回null即可，我们假设是有环的，那么会有两种情况，一种是O型，一种是6型，其实原理都一样，这里主要看一下6字型的环，他会有两种情况，

一种是环很大，如下图所示。

如果有环，那么快指针走过的路径就是图中a+b+c+b，慢指针走过的路径就是图中a+b，因为在相同的时间内，快指针走过的路径是慢指针的2倍，所以这里有a+b+c+b=2*(a+b)，整理得到a=c，也就是说图中a的路径长度和c的路径长度是一样的。

在相遇的时候再使用两个指针，一个从链表起始点开始，一个从相遇点开始，每次他们都走一步，直到再次相遇，那么这个相遇点就是环的入口。


还有一种情况就是环很小，如下图所示

这种情况下当快慢指针在环上相遇的时候，快指针有可能在环上转了好几圈，我们假设相遇的时候快指针已经在环上转了n圈。

那么相遇的时候快指针走过的路径就是a+b+(b+c)*n，（b+c其实就是环的长度），慢指针走过的路径是a+b。由于相同时间内快指针走过的路径是慢指针的2倍。

所以有a+b+(b+c)n=2(a+b)，整理得到a+b=n*(b+c)，也就是说a+b等于n个环的长度。

我们还可以使用两个指针，一个从链表的起点开始，一个从相遇点开始，那么就会出现一种情况就是，一个指针在路径a上走，一个指针一直在环上转圈，最终会走到第一种情况。

所以无论哪种情况我们都可以使用第一种方式解决，代码如下 

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        slow = pHead
        fast = pHead
        while fast !=None and fast.next !=None:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                while pHead != slow:
                    pHead =pHead.next
                    slow = slow.next
                return slow
        return None
参考资料：