給一個鏈表账蓉，若其中包含環(huán)枚碗，請找出該鏈表的環(huán)的入口結(jié)點，否則剔猿，輸出null视译。
一. 什么是鏈表的環(huán)？
單鏈表出現(xiàn)循環(huán)的情況就是鏈表的環(huán)归敬。
所以酷含，尋找環(huán)的入口就是找到循環(huán)開始的地方。
二. 解決方案
-
快慢指針
-
理解該方法需要我們推導(dǎo)一條原理
- 如圖所示汪茧，
x為鏈表入口到環(huán)入口的距離椅亚，y為環(huán)入口到快慢指針相遇點的距離，z為相遇點到環(huán)入口的距離舱污。 - 同時呀舔，環(huán)的總長度為L，即
L = y + z扩灯。 - 設(shè)置快指針媚赖，每次走2個節(jié)點，記為2S珠插。
-
設(shè)置慢指針惧磺，每次走1個節(jié)點，記為1S捻撑。
- 化簡得到：
x = (n - 1)L + z磨隘。 - 其中
n是快指針比慢指針多走的循環(huán)數(shù)缤底，當n = 1時，x = z番捂，也就是說个唧，當快指針只比慢指針多走一圈就相遇的話，鏈表入口到環(huán)入口的距離=相遇點到環(huán)入口的距離设预。當n != 1時徙歼，道理一樣，只不過快指針跑多幾圈而已絮缅。 - 正是基于上面的結(jié)論鲁沥，可以在快慢指針第一次相遇的地方重置快指針的位置，使快指針回到鏈表入口耕魄，慢指針不動。然后彭谁，兩個指針以相同的速度在運動吸奴，再次相遇的地方就是環(huán)入口。
-
理解該方法需要我們推導(dǎo)一條原理
function EntryNodeOfLoop(pHead)
{
let fast = pHead;
let slow = pHead;
while(fast && fast.next){
fast = fast.next.next;// 快指針一次走兩步
slow = slow.next;// 慢指針一次走一步
if(fast == slow){ // 第一次相遇重置快指針的位置以及速度
fast = pHead;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;// 再次相遇的地方就是環(huán)入口
}
}
return null;
}
