题解 | #链表中环的入口结点#

法一：双指针。 参考讨论区却顾所来径的清晰解释思路。

设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点（结论1）。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口（结论2）。

两个结论： 1、设置快慢指针，假如有环，他们最后一定相遇。 2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。

两个结论证明参见讨论区

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        #空链表判断
        if pHead==None or pHead.next==None:#注意：'NoneType' object has no attribute 'next'。如果phead为空，不能pHead.next.next
            return None
        fast=pHead.next.next#如果写fast=pHead，slow=pHead，那么fast直接等于slow，下面不好循环
        slow=pHead.next
        #第一，先找相遇点        
        while fast !=slow:
            if fast==None:#如果.next遇到空节点，说明走到底了，没有环
                return None
            fast=fast.next.next
            slow=slow.next
        #第二，找环入口。两个指针分别从链表头和相遇点继续出发，每次走一步
        fast=pHead
        while fast !=slow:
            fast=fast.next
            slow=slow.next
        return fast

时间复杂度：O(n)，需要将链表的所有结点遍历一遍

空间复杂度：O(1)，需要额外两个快慢指针来遍历结点。

法二：哈希表。 最常规易懂的解法，遍历整个链表结点，然后用哈希表（可以用集合）来存储已访问过的结点，最后进行对比。若该结点已存在哈希表中，则代表该结点是我们要找的环形链表的入口结点；否则把结点添加到哈希表中，继续往下遍历。可参考题解区不是江小白的代码。

时间复杂度：O(n) (因为最糟糕的情况就是遍历了整个链表，n 代表链表中的结点数）

空间复杂度：O(n) (最糟糕的情况是把整个链表的结点插入哈希表中）