题目描述
给定一个链表,若其中包含环,则输出环的入口节点。
若其中不包含环,则输出null。
样例
给定如上所示的链表:
[1, 2, 3, 4, 5, 6]
2
注意,这里的2表示编号是2的节点,节点编号从0开始。所以编号是2的节点就是val等于3的节点。
则输出环的入口节点3.
算法1
设置快慢指针,快指针一次走两步 慢指针一次走一步
如果存在环,那么快指针一定可以追得上慢指针,并且追上的时候的位置一定在环中
设头节点到环的入口距离为a,环的长度为r,快慢指针相遇点距离环的入口为b
因为快指针走过的距离是慢指针的2倍 所以就有 2(a+b)=nr+a+b (n表示快指针走过的环的圈数)
化简得:a=nr-b=(n-1)r+r-b
所以我们发现从头节点到环入口的距离等于快慢指针相遇点到环入口的距离,所以可以利用和这个性质求出环的入口
Java 代码
class Solution {
public ListNode entryNodeOfLoop(ListNode head) {
if(head==null) return null;
ListNode s=head;
ListNode f=head;
while(s!=null&&f!=null){
s=s.next;
f=f.next.next;
if(s==f){
break;
}
}
if(s==null||f==null) return null;
ListNode p1=s;
ListNode p2=head;
while(p2!=p1){
p2=p2.next;
p1=p1.next;
}
return p1;
}
}