力扣刷题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.next
    • fast = fast.next

• 两者最终相遇（具体可查看下面详细的数学推导）：

  • 当两者再次相遇时slow == fast，位置就是环的入口节点，也就是兔子撒尿炫耀的地方。

---

举报成功：

• 裁判员找到了兔子撒尿标记的地方（环的入口节点）并提交结果return slow，乌龟举报成功，取消兔子的比赛成绩。

---

复杂度

• 时间复杂度：O(n）

  • 每次兔子和乌龟各走一段路，总路程不会超过链表长度的两倍。

• 空间复杂度：O(1)

  • 只用了两只小动物（两个指针变量），省吃俭用，不多花内存。

---

记忆秘诀

1. 乌龟走一步，兔子跳两步。
2. 链表有环，相遇无误。
3. 链表无环，兔子先停步。
4. 环点未锁住，乌龟再起步
5. 兔子陪跑步，入口终汇聚

---

补充：数学推导

设链表为一个带环的结构，其中：

• 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 = pHeadfast = pHead# 检测是否有环while fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:  # 快慢指针相遇，说明有环breakelse:return None  # 如果没有环，返回 None# 重新开始寻找环的入口slow = pHead  # 慢指针重新指向头节点while slow != fast:slow = slow.nextfast = fast.next  # 两个指针每次都走一步# 相遇时即为环的入口return slow

---

* 欢迎大家探讨新思路，能够更好的理解和记忆