前置问题:判断链表中是否有环?
只需要设置快慢两个指针,快指针每次走两步,慢指针每次走一步。
如果快指针直到遍历结束都没有与慢指针相遇,则链表中无环;否则有环。
快慢指针
将链表分为两段:无环段长度为 $a$,环段长度为 $b$。
当快慢指针相遇时,设 慢指针走了 $x$ 步,则快指针走了 $2x$ 步,那么快指针比慢指针多走了 $k$ 圈,即 $2x - x = kb$,也即 $x = kb$($k$ 为正整数)。
注意,此时慢指针再走 $a$ 步,就可以恰好到达环的起点。
为什么?因为 $x + a = kb + a$,正好是从起点出发,走一段无环 $a$,再走 $k$ 圈环。
已知上面的结论,就好办了
此时在起点处设置一指针 $p$,让 $p$ 与慢指针 $slow$ 一起走,走了 $a$ 步后会在环的起点处相遇,即得到环的起点。
时空复杂度
- 时间复杂度:$$
- 空间复杂度:$$
Java 代码
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution {
public ListNode entryNodeOfLoop(ListNode head) {
if (head == null) {
return null;
}
// 快慢指针
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// 快慢指针相遇,说明链表有环
if (fast == slow) {
// 此时 slow 距离环的起点的距离恰好是 a
ListNode p = head;
while (p != slow) {
slow = slow.next;
p = p.next;
}
// slow 与 p 相遇的位置一定是环的起点
return slow;
}
}
// 链表无环,返回 null
return null;
}
}
题外话:慢指针第一圈走不完,就一定会和快指针相遇
解释:
- 快指针先进入环
- 当慢指针刚到达环的入口时,快指针此时在环中的某个位置(也可能此时相遇)
- 设此时快指针和慢指针距离为 $x$(若在第二步相遇,则 $x = 0$)
- 设环的周长为 $n$,那么看成快指针追赶慢指针,需要追赶 $n-x$;
- 设慢指针速度 $1/s$,快指针 $2/s$,快指针每次都追赶慢指针 $1$ 个单位,那么追赶需要 $(n-x)s$
- 在 $n-x$ 秒内,慢指针走了 $n-x$ 单位,因为 $x\ge 0$,则慢指针走的路程小于等于 $n$,即走不完一圈就和快指针相遇
链表中环的相关问题:
-
链表中是否存在环?
-
若存在环,找出环的入口节点
-
若存在环,求环中节点数
从环中任意节点(如入口节点),开始遍历到再次回到此节点,即可得到环中节点数
orz,解释得太清楚了