链表中环的入口结点

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

思路：无脑法，使用辅助存储空间。

def EntryNodeOfLoop(self, pHead):
    # write code here
    #遍历链表，环的存在，遍历遇见的第一个重复的即为入口节点
    tempList = []
    p = pHead
    while p:
        if p in tempList:
            return p
        else:
            tempList.append(p)
        p = p.next

思路2：快慢指针。快指针一次走两步，慢指针一次走一步，设链表起点到入口结点的长度是x1，快慢指针第一次相遇时距离入口结点的长度是x2，此时慢指针走了x1+x2，快指针走了2x1+2x2，也就是说x1+x2的长度正好是环的一圈大小的倍数。
此时让一个指针从起点出发，一个指针从相遇结点出发，都是一次走一步，当两个指针第一次相遇时恰好是在入口结点。