链表中环的入口结点

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

python2.7解法---是否有环：

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead:
            return None
        pSlow = pHead
        pFast = pHead
        while pSlow != None and pFast.next != None:
            pSlow = pSlow.next
            pFast = pFast.next.next
            if pSlow == pFast:
                return True
        return False

当fast和slow相遇时，slow还没有走完链表，假设fast已经在环内循环了n(1<= n)圈。假设slow走了s步，则fast走了2s步，又由于

fast走过的步数 = s + n*r（s + 在环上多走的n圈），则有下面的等式：

2*s = s + n * r ; (1)

=> s = n*r (2)

如果假设整个链表的长度是L，入口和相遇点的距离是x（如上图所示），起点到入口点的距离是a(如上图所示)，则有：

a + x = s = n * r; (3) 由（2）推出

a + x = (n - 1) * r + r = (n - 1) * r + (L - a) (4) 由环的长度 = 链表总长度 - 起点到入口点的距离求出

a = (n - 1) * r + (L -a -x) (5)

集合式子（5）以及上图我们可以看出，从链表起点head开始到入口点的距离a,与从slow和fast的相遇点（如图）到入口点的距离相等。
因此我们就可以分别用一个指针（ptr1, prt2），同时从head与slow和fast的相遇点出发，每一次操作走一步，直到ptr1 == ptr2，此时的位置也就是入口点！

python2.7解法---环的入口：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead:
            return None
        pSlow = pHead
        pFast = pHead
        while pSlow != None and pFast.next != None:
            pSlow = pSlow.next
            pFast = pFast.next.next
            if pSlow == pFast:
                break
        if pSlow == None or pFast.next == None: return None
        pFast = pHead
        while pFast != pSlow:
            pFast = pFast.next
            pSlow = pSlow.next
        return pFast