.jpg)
804 字
4 分钟
环形链表 II
题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
解题思路
- 双指针判环：
- 快指针（每次2步）和慢指针（每次1步）同时出发
- 若两指针相遇则存在环
- 重置指针定位入口：
- 相遇后将慢指针重置到头节点
- 两指针同速移动（每次1步）
- 二次相遇即入口：
- 当两指针再次相遇时即为环入口
- 无环处理：
- 若快指针先到链表尾则返回null
关键洞察
- 数学关系核心：
- 设头到入口距离a，入口到相遇点距离b，相遇点到入口距离c
- 快指针路程 = 2 × 慢指针路程 ⇒ a + k(b+c) + b = 2(a + b) ⇒ a = c + (k-1)环长
- 重置指针原理：
- 第二次同速移动时，两指针将在环入口相遇
- 通用性保证：
- 无论环大小如何均适用
- 快慢指针首次相遇点不影响结论
- 边界处理：
- 单节点自环的特殊处理
- 无环链表的快速判定
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)：每个节点最多遍历两次 |
| 空间复杂度 | O(1)：仅需两个指针 |
| 最优情况 | O(n)：当环在链表头部时 |
代码实现
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
/** * @param {ListNode} head * @return {ListNode} */var detectCycle = function (head) { let slow = head, fast = head; while (true) { if (!fast || !fast.next) return null; slow = slow.next; fast = fast.next.next; if (slow === fast) break; } fast = head; while (slow !== fast) { slow = slow.next; fast = fast.next; } return fast;};实际应用场景
- 内存泄漏检测：检测程序中循环引用的对象链`
- 路由检测：网络路由中检测环形路径`
- 状态机验证：验证有限状态机是否陷于死循环`
- 链表操作安全：链表排序/合并前确保无环`
变种：求环长度
const cycleLength = (head) => { // 先找到相遇点 let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) break; }
// 无环返回0 if (!fast || !fast.next) return 0;
// 固定相遇点，移动指针计算环长 let current = slow; let length = 0; do { current = current.next; length++; } while (current !== slow);
return length;};多指针实现对比
| 方法 | 空间复杂度 | 是否修改链表 | 适用场景 |
|---|---|---|---|
| 双指针法 | O(1) | 否 | 通用最优解 |
| 哈希表法 | O(n) | 否 | 需记录访问节点 |
| 标记节点法 | O(1) | 是 | 允许修改链表结构 |
| 破坏链表法 | O(1) | 是 | 只允许临时修改 |
相似题目
- [[环形链表]]
- 寻找重复数