题目描述
一个链表中包含环,请找出该链表的环的入口结点。
解题思路
两个结点同时运行,其中快结点 fast 一次走两个结点,慢结点 slow 一次走一个结点。
假设 x 为环前面的路程(黑色路程),a 为环入口到相遇点的路程(蓝色路程,假设顺时针走), c 为环的长度(蓝色 + 橙色路程)
两结点相遇时,快结点走过的路程:
L_f=x+n*c+a
慢节点走过的路程:
L_s=x+m*c+a
且速度 fast 是 slow 的二倍,所以:
L_f=2L_s
于是,可以推出:
x=(n-2*m)*c-a=(n-2*m-1)*c+c-a
也就是说,环前面的路程=环长度的整数倍 +c-a。
而 c-a 就是橙色部分,也就是从起点走到入口点的路程相当于走几个环 + 橙色部分的路径。
那么我们让 slow 在相遇点走,fast 在起始点走(一次只走一个结点),最后一定是在环的入口相遇。
时间复杂度:O(n)
空间复杂度:O(1)
代码
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if (pHead == null || pHead.next == null || pHead.next.next == null)
return null;
ListNode slow = pHead.next;
ListNode fast = pHead.next.next;
while (fast != slow) {
if (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
} else
return null;
}
fast = pHead;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于