【忍者算法】从入环点到相遇点：深入理解环形链表 II｜LeetCode第142题 环形链表 II

【忍者算法】从入环点到相遇点：深入理解环形链表 II｜LeetCode第142题

问题升级：不止要找环，还要找入环点

在上一题中，我们讨论了如何判断链表是否有环。现在让我们更进一步：如果确定链表中有环，我们该如何找到环的入口节点？这就像是在环形跑道上不仅要确认跑道是环形的，还要找到环形跑道的起点。
问题描述

LeetCode第142题"环形链表 II"要求：给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
例如：

1. 输入：3 → 2 → 0 → -4
2.          ↑___________|
3. 输出：返回节点 2
4. 解释：链表中存在一个环，其尾部连接到第二个节点

复制代码

从快慢指针相遇谈起

还记得上一题中的快慢指针相遇吗？那个相遇点看似随机，实际上蕴含着重要的数学原理。让我们用这个相遇点来找到入环点。
巧妙的数学关系

假设：

• 链表头到入环点的距离为 a
  
• 入环点到相遇点的距离为 b
  
• 相遇点到入环点的距离为 c
  

当快慢指针相遇时：

• 慢指针走过的距离：a + b
  
• 快指针走过的距离：a + b + n(b + c)，其中n是快指针在环内走的圈数
  
• 因为快指针速度是慢指针的两倍，所以：2(a + b) = a + b + n(b + c)
  

通过解这个等式，我们发现：a = c + (n-1)(b + c)
这意味着：从链表头和相遇点同时出发，最终会在入环点相遇！
代码实现

1. public ListNode detectCycle(ListNode head) {
2.     // 处理特殊情况
3.     if (head == null || head.next == null) {
4.         return null;
5.     }
6.    
7.     // 第一阶段：使用快慢指针找到相遇点
8.     ListNode slow = head;
9.     ListNode fast = head;
10.     ListNode intersection = null;
11.    
12.     while (fast != null && fast.next != null) {
13.         slow = slow.next;
14.         fast = fast.next.next;
15.         if (slow == fast) {
16.             intersection = slow;
17.             break;
18.         }
19.     }
20.    
21.     // 如果没有相遇点，说明无环
22.     if (intersection == null) {
23.         return null;
24.     }
25.    
26.     // 第二阶段：从头节点和相遇点同时出发，找入环点
27.     ListNode start = head;
28.     while (start != intersection) {
29.         start = start.next;
30.         intersection = intersection.next;
31.     }
32.    
33.     return start;
34. }

复制代码

图解过程

1. 1) 初始状态：
2. 3 → 2 → 0 → 4
3.     ↑___________|
4. S,F
6. 2) 快慢指针相遇：
7. 3 → 2 → 0 → 4
8.     ↑___________|
9.         S,F
11. 3) 从头和相遇点同时出发：
12. 3 → 2 → 0 → 4
13.     ↑___________|
14. P1      P2
16. 4) 在入环点相遇：
17. 3 → 2 → 0 → 4
18.     ↑___________|
19.     P1,P2

复制代码

与上一题的联系与进阶

相比环形链表I，这一题是一个很自然的进阶：

• 两题都使用了快慢指针技巧
  
• 这一题复用了上一题找相遇点的过程
  
• 在找到相遇点后，增加了寻找入环点的步骤
  

实现细节与优化

• 空间复杂度仍然保持O(1)
  
• 时间复杂度为O(n)
  
• 不需要额外的数据结构
  
• 代码实现优雅且直观
  

思考与延伸

这个问题告诉我们：

• 有时问题的解决方案就藏在问题本身的特性中
  
• 数学关系可以帮助我们找到优雅的解法
  
• 快慢指针不仅能检测环，还能帮我们找到关键节点
  

实际应用思考

这个算法的思想可以应用在很多实际场景中：

• 检测循环依赖
  
• 死锁检测
  
• 循环引用的处理
  

让我们记住：当我们遇到类似的"寻找特殊点"问题时，可以尝试利用路径特性来找到优雅的解决方案。
作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！