剑指offer——链表中环的入口节点

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

解答如下：
环境：python 2.7.3

本题的思路是设置快指针fastPointer，步长为2，设置慢指针，步长为1。循环先移动慢指针再移动快指针，然后判断它们是否相遇，如果相遇了则说明链表有环，否则链表没有环。
当它们相遇时，我们可以知道，快指针走过的总步数是满指针走过总步数的两倍。
（1）我们设L为慢指针走过的步数为L，那么2L = L。
（2）设从表头走到入口点需要S步。
（3）设慢指针在相遇前在环内走了d步。
（4）设慢指针再走m步，又可以到达入口点，也就是d+m等于一个循环。
那么：
slowPointer的步长L = s + d
fastPointer的步长2L=n(m+d) + s + d #n表示快指针绕环次数
联立两式：s = m + (n-1)(m+d) #可知，从表头走步长为1的s步和从相遇点再走步长为1的m步的再次相遇点为环入口点。

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        #判断链表有没有环,定义快慢指针，快指针步长2，慢指针步长1.
        #要么快指针为空（没有环）,要么快慢重合（有环）。
        if pHead == None:
            return None
        
        fastPointer = pHead
        slowPointer = pHead
        
        circle = False #默认没有环
        while fastPointer and fastPointer.next:
            fastPointer = fastPointer.next.next
            slowPointer = slowPointer.next
            if fastPointer == slowPointer:
                circle = True
                break
        if circle != True:
            return None
        
        #快慢指针行走的步数始终是相等的,设步数为L。
        #slow总步长为L，fast总步长为2L.
        #假设开始到入口点长度为s，slow在环内走了d。
        #slowPointer的步长L = s + d
        #fastPointer的步长2L=n(m+d) + s + d
        #联立两式：s = m + (n-1)(m+d)
        
        fastPointer = pHead
        while fastPointer != slowPointer:
            fastPointer = fastPointer.next
            slowPointer = slowPointer.next
            
        return fastPointer