CodingInterviews
CodingInterviews copied to clipboard
链表中环的入口结点的双指针简单解法
基本思路
- 两个指针,a每次走一步,b每次走两步
- 相遇后,a设为list的开头,b不变,然后a、b同时走直到相遇
证明
- 设
- 第一次,经过
k
步相遇 - 链的起点到环的起点为
s
长度 - 环的起点到第一次相遇的点距离为
m
- 环的长度为
r
- 第一次,经过
- 所以
-
2k-k=nr=r
-
s=k-m=r-m
- 因为
a
走了不到整条链,比整条链少r-m
长度,然后b
走了整条链加上m
长度 -
b
比a
多走的可以分成两段- 第一部分是从相遇点到环的终点
- 第二部分是从环的起点到相遇点
- 第二部分
a
也走过(所以这一部分b
刚好走过两倍a
走过的长度) - 所以,第一部分就是等价于
a
从链的起点到环的起点
- 因为
- 从而,只要一起再走
r-m
步就可以相遇
-
代码
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode p1 = head, p2 = head;
while (p1 != null && p2 != null) {
p1 = p1.next;
if (p2.next == null) {
return null;
}
p2 = p2.next.next;
if (p1 == p2) {
break;
}
}
if (p1 == null || p2 == null) {
return null;
}
p1 = head;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}