LeetCode 141. 环形链表
题目描述
题意分析
从头节点开始不断沿
next向后走，如果会再次到达已经访问过的同一个节点，链表就有环；如果最终走到空节点，就没有环。返回是否存在环，不需要返回环的入口，也不能通过修改指针来做标记。这里的“同一个节点”指同一个对象，节点值相等不能说明有环。空链表没有环；只有一个节点时，要看它的后继是否指回自身，不能仅凭节点数量判断。
解法：Floyd 快慢指针
核心思路
[!blue]
用集合记录经过的节点可以判断重复访问，但需要额外空间。要省掉这份记录，可以让两个指针以不同速度沿同一条链移动：
slow每轮走一步，fast每轮走两步，观察它们是否会在移动后到达同一个节点。如果没有环，链表是一条有限路径。快指针不断前进，最终一定会到达空节点，或停在后继为空的尾节点，因此循环能够结束。
如果存在环，快指针不会走到空节点；当慢指针进入环时，快指针也已经在环中。设环长为
c，每轮快指针相对慢指针多走一步，两者的位置差按模c依次变化，至多再走c轮就会变成0，也就是相遇。这说明有环时一定能找到相遇点，不需要无限等待。两个指针都从头节点出发，初始相同没有判定意义，所以必须先移动再比较。比较的是节点引用；一旦移动后相遇，就说明快指针通过环绕重新追上了慢指针。
解题步骤
- 令
slow、fast都指向head。- 每轮先检查
fast和fast.next都非空，保证两步移动不会解引用空节点。- 将
slow移动到后继，将fast移动到后继的后继。- 移动后若
slow == fast，说明有环，立即返回true。- 若循环因为快指针走到末尾而结束，返回
false。空链表会直接走到这一步。
代码实现
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// 快指针要访问两步，先保证两个入口都存在。
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
// 先移动再比较节点身份，避免把初始重合当作有环。
if (slow == fast) {
return true;
}
}
return false;
}
}
func hasCycle(head *ListNode) bool {
slow := head
fast := head
// 快指针要访问两步，先保证两个入口都存在。
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
// 先移动再比较节点身份，避免把初始重合当作有环。
if slow == fast {
return true
}
}
return false
}
复杂度分析
设
n为从头节点出发能够到达的不同节点数。
- 时间复杂度：$O(n)$。无环时快指针最多走完链表；有环时，慢指针先经过环外前缀，再经过至多一圈就会与快指针相遇。
- 空间复杂度：$O(1)$，只使用快、慢两个指针。
关键点总结
[!green]
- 两个指针速度不同，才能让环内的相对位置持续变化，并保证最终相遇。
- 快指针是否走到空节点区分了无环情况，移动后是否相遇区分了有环情况。
- 判断相遇只比较节点身份，不依赖节点值，也不修改链表。
易错点总结
[!yellow]
- 只检查
fast != null就访问fast.next.next，在快指针位于尾节点时会触发空指针异常。- 在第一次移动前比较两个指针，会把它们初始都指向头节点误当成有环证据。
- 用节点值判断相遇，会把值相同的不同节点误认为同一节点。
- 相遇点不一定是环入口。本题只返回布尔值，不能把这段代码的相遇位置直接当作另一道题要求的入口。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 142. 环形链表 II | 中等 | 快慢指针相遇提供有环判定，原题进一步把指针移回链头求入环点。 |
| 202. 快乐数 | 简单 | 把数字变换视为下一状态，同样可用快慢指针判断过程是否进入循环。 |
| 287. 寻找重复数 | 中等 | 用快慢指针确定环或中间位置；本题判断链表是否存在环，该题将数组值视为后继指针寻找重复入口。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！