AcWing 34. 链表中环的入口结点 只需掌握两个点就可以
原题链接
中等
作者:
henhen敲
,
2020-05-15 23:00:09
,
所有人可见
,
阅读 596
快慢指针法 其实本题只需掌握两个点就可以了
首先令first second 分别为每次走一步 走两步的指针
第一个时间点:当first刚好经过x步进入环的入口e时 second已经走了2x个node 且已经在环中 走了x个node了
此时令second与first距离y个node 同时也可指 环的大小整数倍为x+y
第二个时间点: 当两者相遇时 一定是在距离入口点y的地方 只需在经过x个node又回到入口了 这是让first从起点开始
second从现在的点开始 每次一步 最终一定会相遇
class Solution {
public ListNode entryNodeOfLoop(ListNode head) {
if(head==null||head.next==null) return null;
ListNode first = head;
ListNode second = head;
do{
if(first.next!=null) first = first.next;
else return null;
if(second.next!=null&&second.next.next!=null) second = second.next.next;
else return null;
if(first==second) break;
}while(true);
first = head;
while(first!=second){
first = first.next;
second = second.next;
}
return first;
}
}