力扣刷题TOP101：6.BM7 链表中环的入口结点
目录：
目的
思路
复杂度
记忆秘诀
python代码
目的
{1,2},{3,4,5}, 3 是环入口。
思路
这个任务是找到带环链表的环入口。可以看作是上一题龟兔赛跑（Floyd 判圈算法）的延续版：乌龟愤愤不平地举报兔子跑得太快，偷偷回头朝自己炫耀得瑟，还说在环口撒了尿标记。裁判接到举报，准备调取“监控记录”，验证兔子是否偷偷回头，并定位撒标记的位置（环入口）。
裁判开始审理过程：
-
参赛选手：
- 乌龟（慢指针slow）： 每次只走一步，慢悠悠的。slow = head
- 兔子（快指针fast）： 从同样的起点出发，每次跳两步，永远快人一步。fast = head
- 观察双方起点位置，从同样的起点出发
比赛规则：
只要兔子还没跑出链表（
fast != None且fast.next != None），比赛继续。
- 为什么检查两个条件？
fast： 如果fast == None，说明兔子已经跑到了链表的尽头，没有环。fast.next： 是兔子跳两步时需要访问的下一个节点。fast.next == None，说明兔子已经没有“下一步”可以跳，也意味着链表没有环。
比赛开始：
- 乌龟稳步前进： 走一步，代表慢速slow = slow.next。
- 兔子飞速跳跃： 跳两步，代表快速移动fast = fast.next.next。
- 是否龟兔同镜（相遇点）： 如果他们在一个镜头中出现（
slow == fast），裁判记录兔子回头了，继续调查。如果没有出现（环），直接结束，乌龟举报无效，返回None。 - 为什么一定会相遇？
- 如果链表是闭环，兔子因为步伐更快，最终会在环内兜圈，追上乌龟。
寻找兔子撒尿点（环口）：
裁判让乌龟回到起点：
- 乌龟回到起点，准备和兔子一同慢跑：
slow = pHead。兔子在相遇点陪乌龟慢慢走：
- 这次双方步伐一致，每次只走一步：
slow = slow.nextfast = fast.next两者最终相遇（具体可查看下面详细的数学推导）：
- 当两者再次相遇时
slow == fast，位置就是环的入口节点，也就是兔子撒尿炫耀的地方。
举报成功：
- 裁判员找到了兔子撒尿标记的地方（环的入口节点）并提交结果return slow，乌龟举报成功，取消兔子的比赛成绩。
复杂度
-
时间复杂度：O(n）
- 每次兔子和乌龟各走一段路，总路程不会超过链表长度的两倍。
-
空间复杂度：O(1)
- 只用了两只小动物（两个指针变量），省吃俭用，不多花内存。
记忆秘诀
- 乌龟走一步，兔子跳两步。
- 链表有环，相遇无误。
- 链表无环，兔子先停步。
- 环点未锁住，乌龟再起步
- 兔子陪跑步，入口终汇聚
补充：数学推导
设链表为一个带环的结构，其中：
- a：链表头节点到环入口的距离（环前的直线段）。
- b：环入口到相遇点的距离（在环中的第一部分）。
- c：相遇点到环入口的剩余距离（环中的第二部分）。
- n：兔子绕环的圈数。
-
兔子的距离是乌龟的两倍：
2(a+b)=a+b+n(b+c)- 兔子每次跳两步，乌龟每次走一步，因此兔子走的距离总是乌龟的两倍。
-
化简公式：消去公共项 a+b，得到：a=c+(n−1)(b+c)
-
乌龟的距离：当乌龟从起点走 a距离时，会刚好到达环的入口。
-
兔子的距离：兔子从相遇点出发，绕过 c距离后也会到达环的入口。
-
同步抵达环入口：因为 n−1表示兔子可能多绕了若干圈，但最终兔子和乌龟都会同时抵达环入口。
-
-
找到环入口的核心原因：
- 相遇后，将乌龟放回起点，兔子留在相遇点。
- 两者按相同速度行进（每次一步），兔子绕过剩余的 c 距离时，乌龟正好走完 a，两者在环入口相遇。
python代码
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead: ListNode) -> ListNode:
# 快慢指针法：检测环
slow = pHead
fast = pHead
# 检测是否有环
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # 快慢指针相遇，说明有环
break
else:
return None # 如果没有环，返回 None
# 重新开始寻找环的入口
slow = pHead # 慢指针重新指向头节点
while slow != fast:
slow = slow.next
fast = fast.next # 两个指针每次都走一步
# 相遇时即为环的入口
return slow* 欢迎大家探讨新思路，能够更好的理解和记忆