環形鏈表II
- Part I、回顧環形鏈表I
- 1、快慢指標思想
- 2、追及思想
- 3、關于n = x的補充
- Part II、環形鏈表進階
- 1、題目簡介
- 2、題目分析
- Part III、總結
Part I、回顧環形鏈表I
環形鏈表I的詳細內容可以參考我們之前一期的文章
《演算法熱門：環形鏈表I(LeetCode 141》)
這一期，我們將在上一期的基礎上再拓展新的內容，不過在此之前，先簡單回顧一下環形鏈表I的主要思想：
1、快慢指標思想
我們定義快、慢兩個指標，假設慢指標一次走一個結點，快指標一次走兩個結點，那么快指標必然會在慢指標之前走到鏈表環的入口點——
當鏈表的頭到環的入口之間的距離足夠大而環的長度又比較小時，由于快指標先入環，那么在慢指標好不容易走到換入口時，快指標可能已經在環內繞了N圈了，其中N≥0，N∈N*
當這種回圈再進行下去，fast指標如果追上slow指標，就能判斷出，鏈表有環；
問題來了，fast指標真的會追上slow指標嗎？
2、追及思想
我們假設鏈表的頭到環的入口的距離為L，環的長度為C，slow進入環后，與fast之間的距離為X；
(由于slow和fast都是順時針走的，這里取順時針間距，如上圖所示)
由于fast指標一次走兩個節點，slow一次走一個節點，也就是說，fast指標比slow指標多走一步，那么如果它們繼續走下去，則fast指標必然會追上slow；
如果還不理解，我們不妨把這樣的一個追逐問題化為一條直線上的追逐問題：
假設還需走n次fast追上slow，那么也就是說：
解出來：n=x
也就是說，只要這樣的回圈再進行x次，fast必然會追上slow；
另一方面考慮，如果鏈表沒有環，那么由于fast走得快，slow永遠不可能追上它，從而我們可以判定：環存在！
3、關于n = x的補充
值得一提的是，由于x是慢指標入環的時候，快慢指標之間的距離，那么這里x必然會小于等于C-1，其中C是環的長度，
原因也很簡單：因為此時快指標和慢指標都已經在環里了，那么最好的情況是這樣：
最壞的情況就是：
由于fast指標走n次就可以追上慢指標，且n=x，那么由此我們可以斷定：在慢指標剛入環還沒走完一圈時，就會被快指標追上！
Part II、環形鏈表進階
1、題目簡介
當我們有能力判斷一個鏈表是否帶環的時候，我們能否更進一步，把環形鏈表的環入口給找到呢？
請看題：
2、題目分析
簡單來說，這題的要求就是：如果鏈表帶環，則回傳環的入口指標，如果不帶環，則回傳NULL；
如何實作呢？這跟之前的那題有啥子關聯？有，關聯還很大，
我們同樣采取快慢指標的方法來判斷這個鏈表是否帶環，如果帶環，則快慢指標必然相遇在環內的某個地方，如圖：
假設從鏈表的頭指標到環的入口，這一段的距離為L，快慢指標的相遇點到環入口，這一段的距離為X，環的長度為C，
由于慢指標在環內還沒走完一圈就會被快指標追上，所以當快慢指標相遇時，慢指標走的距離為L+X，
（詳細原因見Part I 中第三點：關于n=x的補充）
當L足夠大而C又比較小時，由于快指標先入環，那么在慢指標好不容易走到換入口時，快指標可能已經在環內繞了N圈了，因此當快慢指標相遇時，快指標走的距離為L+X+NC（N≥0，N∈N）
由于快指標的步長是慢指標的兩倍，所以快指標走的距離也是慢指標走的距離的兩倍即:
2 * (L + X) = L + X + N * C
由此得到
L= N * C - X = (N - 1) * C + C - X
那么，如果此時一個指標p1從鏈表的頭出發，另一個指標p2從快慢指標的相遇點出發，兩指標的步長都為1，則經過(N - 1) * C + C - X次的移動，p1從鏈表的頭走過L這段距離來到環的入口，p2走了 (N - 1) * C步回到相遇點，又走了C - X步來到了環的入口，此時，p1=p2=環入口的指標，
理論分析結束，代碼實作：
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode* slow = head, *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)//slow和fast相遇，鏈表帶環
{
struct ListNode* p1 = head, *p2 = slow;//p1從鏈表的頭出發，p2從相遇點出發
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;//p1和p2相等時，回傳任意一個
}
}
return NULL;
}
Part III、總結
這是一道非常值得收藏回味的題，和環形鏈表I類似，環形鏈表II的代碼實作同樣很簡單，但是關于鏈表帶環的題目最重要的是實作背后的邏輯推理和分析，
本題還有另外一個解題思路，需要一定的鋪墊，放在之后介紹~
創作不易，留個點贊評論再走吧~關注我，定期分享更多學習、刷題經驗
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/291861.html
標籤：其他