如何判斷一個單鏈表是否有環(huán)？有環(huán)的話返回進(jìn)入環(huán)的第一個節(jié)點的地址，無環(huán)的話返回空。如果鏈表的長度為N，請做到時間復(fù)雜度O(N)，額外空間復(fù)雜度O(1)。
策略
-
定義fast和slow指針；
- 前者一次走兩步，后者一次走一步；走完之后做一次結(jié)算：
- 如果前者越界，說明無環(huán)
- 如果兩者相遇，說明有環(huán)
-
若相遇，slow回到頭結(jié)點，開始繼續(xù)走。但這次fast和slow每次均走一步。
-
兩者相遇點即為入環(huán)結(jié)點。
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;
}
簡略證明
設(shè)鏈表非環(huán)內(nèi)結(jié)點數(shù)目是m1
環(huán)內(nèi)結(jié)點數(shù)目是m2
(本例子中，m1=3 m2=6)
慢指針在第n步會到達(dá)n結(jié)點
快指針在第n步會到達(dá)
- 2n (2n<=m1)
- m1+(2n-m1)%m2 (2n>m1)
如果兩者第一次相等，則快指針到達(dá) m1+[(2n-m1)-m2]=2n-m2
聯(lián)立求得 n=m2
也就是說，第一次相遇時的地點是m2號結(jié)點。因為鏈表前段有m1個非環(huán)結(jié)點，所以m2號結(jié)點如果想走到入環(huán)點，需要走：m2-(m2-m1)=m1步
此時如果慢指針從頭開始走，也需要走m1步
所以兩者會相遇在入環(huán)點。
