.jpg)
527 字
3 分钟
环形链表
题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
解题思路
- 快慢指针策略：
- 初始化慢指针（每次移动1步）和快指针（每次移动2步）
- 两指针从链表头部同时出发
- 相遇检测：
- 若存在环，快指针最终会追上慢指针（相遇）
- 若不存在环，快指针先到达链表尾部（
null）
- 边界处理：
- 检查快指针及其下一节点是否为空
- 空链表或单节点链表直接返回
false
关键洞察
- 追及原理：
- 在环中，快指针每步追近1个节点（速度差1步/周期）
- 环内节点数为N时，至多N步后必然相遇
- 起点无关性：
- 无论环在何处，快慢指针终会相遇（环必然存在闭环路径）
- 效率优势：
- 空间复杂度 O(1)，无需额外存储
- 时间复杂度 O(n)，最坏情况遍历所有节点
- 安全移动：
- 快指针每次移动需检查两步（当前和下一节点）
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)：无环时遍历 n/2 节点；有环时最多 n 步相遇（n 为节点数） |
| 空间复杂度 | O(1)：仅使用两个指针，常数额外空间 |
代码实现
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
/** * @param {ListNode} head * @return {boolean} */var hasCycle = function (head) { if (!head) { return false; } let slow = head, fast = head.next; while (fast && fast.next) { if (slow === fast) return true; slow = slow.next; fast = fast.next.next; } return false;};相似题目
- [[环形链表 II]]
- 快乐数