链表中环的入口结点 -- 每日一题03

# 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。 
#  数据范围： ， 要求：空间复杂度O1 ，时间复杂度On 
#  例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示： 
#  可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
#  Related Topics 链表 哈希 双指针 
# 示例:
# 输入:{1,2},{3,4,5}
# 输出:3
'''
使用快慢指针，快指针每次走俩步，慢指针每次走一步
设链表头到环入口为 X,环入口到相遇处为 Y
则慢指针走了X+Y的距离，快指针走了2(X+Y)的距离
慢指针在环上走了Y距离，快指针在环上面走了X+Y的距离，则环长度为X+Y
相遇点到环入口的距离与头指针到环相遇点的距离相同
之后让头指针与慢指针同时出发，每次走一步，头指针与慢指针相遇时即是环的入口
'''
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        fast = pHead
        slow = pHead
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                break
        if fast is None or fast.next is None:
            return None
        while pHead != slow:
            pHead = pHead.next
            slow = slow.next
        return slow