如何判断一个单链表是否有环？有环的话返回进入环的第一个节点的地址，无环的话返回空。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1)。
策略
-
定义fast和slow指针；
- 前者一次走两步，后者一次走一步；走完之后做一次结算：
- 如果前者越界，说明无环
- 如果两者相遇，说明有环
-
若相遇，slow回到头结点，开始继续走。但这次fast和slow每次均走一步。
-
两者相遇点即为入环结点。
CODE
ListNode* chkLoop(ListNode* head) {
if(!head || !head->next)
return nullptr;
ListNode* H=new ListNode(0);
H->next=head;
ListNode *fast=H,*slow=H;
while(fast->next && fast->next->next){
fast=fast->next->next;
slow=slow->next;
if(fast==slow){
break;
}
}
if(fast!=slow)
return nullptr;
slow=H;
while(fast!=slow){
fast=fast->next;
slow=slow->next;
}
delete H;
return fast;
}
简略证明
设链表非环内结点数目是m1
环内结点数目是m2
(本例子中，m1=3 m2=6)
慢指针在第n步会到达n结点
快指针在第n步会到达
- 2n (2n<=m1)
- m1+(2n-m1)%m2 (2n>m1)
如果两者第一次相等，则快指针到达 m1+[(2n-m1)-m2]=2n-m2
联立求得 n=m2
也就是说，第一次相遇时的地点是m2号结点。因为链表前段有m1个非环结点，所以m2号结点如果想走到入环点，需要走：m2-(m2-m1)=m1步
此时如果慢指针从头开始走，也需要走m1步
所以两者会相遇在入环点。
