1.易懂 常规思路
首先这题要我们找链表的环入口结点，最常规易懂的解法就是遍历整个链表结点，然后用哈希表来存储已访问过的结点，最后进行对比。 若该结点已存在哈希表中，则代表该结点是我们要找的环形链表的入口结点；否则把结点添加到哈希表中，继续往下遍历。
2.图解 哈希表解法
这里我们就用题目中给的三个示例来解释一下上面的具体操作👇，首先是第一个示例：
输入：{1,2},{3,4,5}
返回值：3
上图表示边遍历链表，边把已访问过的结点存入哈希表中
然后到最后一个结点的时候，指针又回到node3 的位置，这就表明这里存在一个环形链表。而node3就是区别这个环形链表的入口结点！！！
下面看第二个示例的哈希表图解👇：
同理第三个示例👇：
3.核心代码
相信到这里大家应该很明白哈希表解法了，下面是核心代码：
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
#创建个已访问过结点的哈希表
nodes = set()
#首先判断链表有无成为环的结点：
while pHead: #有结点的情况下：
if pHead in nodes: #如果结点存在于哈希表中，就返回结点
return pHead
else:
nodes.add(pHead) #否则把结点添加到哈希表中
pHead = pHead.next #继续遍历下一个结点
return None #无结点就返回None
4. 复杂度分析
时间复杂度：O(n) (因为最糟糕的情况就是遍历了整个链表，n 代表链表中的结点数）
空间复杂度：O(n) (最糟糕的情况是把整个链表的结点插入哈希表中）
可以看出此法虽然易懂但不是最优，所以还需优化。
--------------------------------------------我是解法二的分割线----------------------------------------------------
5. 解法二：双指针
解法一的哈希表虽然简单易懂，但是空间复杂度为O(n)，这里我们还可以进行优化，使用 双指针方法即可让它变为O(1)的空间复杂度；下面依然是图解示例进行解说。
5.1 思路+图解
- 首先我们创建快、慢两个指针（fast、slow），然后fast指针一次走2步；slow指针一次走 1步。
- 接着我们需要先判断：是否存在环？如果不存在，则直接返回None；否则fast、slow指针一定会相遇。
- 当环存在的时候，假设环之前有m个节点，环之内有n个节点；且slow指针已经走了j 步，我们可以发现第一次两指针相遇时，fast指针走过步数为：
fast = j + i*n ( i 表示fast指针比slow指针多走了 i 个环）
同样根据一开始的fast、slow定义，fast指针的步数也可以这样表达：fast = 2*slow = 2j。 带入上面的等式，可以解出👉j = i*n 的等式。- 所以可知fast = 2 * i * n ， slow = i * n，这说明了fast指针和slow指针第一次相遇的时候都走过了环的倍数！！！ 然后再走 j 步就是环的入口节点。
- 接下来让 fast从链表头部再次出发，而slow 则位置不变；且fast 和slow 都开始以每次走一步的相同频率继续行进。
- 当fast 走到 j 步的时候，slow 就走了 j + i * n 步，此时 fast和slow两指针重合！这就是我们要找的环入口节点！返回slow，因为它就在入口节点处。
还是看看示例图：
👆上图为不存在环的情况；下面是存在环的情况图解👇：
第一次相遇：
第二次相遇：
5.2 核心代码
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
#创建快、慢两种指针
fast, slow = pHead, pHead
while True:
#第一种结果： fast 指针走过链表末端，说明链表无环，返回 None
if not fast or not fast.next:
return None
#慢指针一次走一步；快指针一次两步
slow = slow.next
fast = fast.next.next
#如果有环，第一次相遇：
if slow == fast:
break
#第二次相遇,fast回到链表起点位：
fast = pHead
#fast、slow两指针不相遇的时候都各走一步：
while slow != fast:
fast = fast.next
slow = slow.next
#再次相遇即slow所在节点
return slow 5.3 复杂度分析
- 时间复杂度：O(n) (其中n为链表中节点的数目,快慢指针走过的距离都不会超过链表的长度)
- 空间复杂度：O(1) (双指针使用常数大小的额外空间)
京公网安备 11010502036488号