Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
給定一個linked list的head,返回linked list中cycle開始的node。如果linked list中没有cycle,回傳 null。
Linked list中存在cycle的條件是,linked list中的某個node可以透過不斷跟隨 next 指針再次被找到。内部使用 pos 來表示尾節點的 next 連接到的node的索引(0-index為基礎)
( → 這句話的意思就是:如果linked list中有cycle的話,那麼pos就是整個cycle的起始位置)。
如果沒有循環,pos 的值等於 -1。請注意,pos 並非作為參數傳遞。
請勿修改linked list。
題目範例如下
對於這題題目,一開始一直卡在要怎麼找到cycle的起始點這個問題上面,沒有把他跟快慢指針聯想在一起,只是按照自己的直覺,先整理出以下幾點:
後來找到了Floyd Cycle Detection Algorithm(又稱為龜兔賽跑算法(Tortoise and Hare Algorithm),解決了以上兩個問題。
在龜兔賽跑算法中,只要烏龜和兔子從起點開始向前奔跑,兩位選手都會 往同一方向 一路跑到終點,那這就表示這條賽道,是一直線通到終點,中間是沒有繞圈的,如下圖:
(烏龜 = 慢指針 , 兔子 = 快指針)
如果在賽道中,兔子雖然一路跑在烏龜前頭,但因為賽道的在距離賽道起點 X 的地方,繞了一個彎,並且繞回前面原本的繞彎處,但是在比賽規則中,烏龜跟兔子都只能向前跑,所以速度較慢的烏龜最後還是在繞彎處遇到跑得快的兔子。
因為兔子跑的速度是烏龜的兩倍,所以跑的距離也是烏龜的兩倍。
利用以上幾點,可以求得整條賽道開始繞彎的位置。
咦? 怎麼突然跳到結論? 我們來看看下面的圖示
1.由上圖可以得到以下結論:
烏龜走的步數 * 2 = 兔子走的步數
2 * (X+A) = X+2A+B
得到→ X = B
2.承上,因X=B代表
只要烏龜從head出發走X步、兔子從node 2(相遇點)出發走B步,
也就是兩指針走相同距離便會在node 1相遇(cycle起始點)
講白話文就是,用烏龜跟兔子的速度歸納出:
1.烏龜跟兔子相遇的位置 與 賽道開始繞彎的位置
2.賽道起點 與 賽道開始繞彎的位置
1.2.距離是一樣的
所以這時,只要讓烏龜跟兔子兩個選手,分別用 一樣的速度,各自從賽道起點、相遇點 同時出發,相遇的中點,就會是 賽道開始繞彎的位置
解釋完概念,回到解題
來看code
var detectCycle = function(head) {
// set slow pointer
let slow = head;
// set fast pointer
let fast = head;
// find the position of node 2 (where two pointers meet)
while(fast && fast.next && fast.next.next){ // while the next node that the fast pointer will move to exists
slow = slow.next;
fast = fast.next.next;
// now pointer2 is at node 2(the meeting point)
if (fast === slow) {
// find the position of node 1 (where the cyle starts)
slow = head;
while (slow != fast){
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
// if there is no cycle
return null;
};
Reference:
https://hackmd.io/@PeterLei/leetcode142