Node 對我來說一直是很似懂非懂的概念,題型有樹狀、鏈節等。因為沒有實際可見的數字或字串等實物可以觀察中間步驟,所以比起其他解題抽象許多。如果光是查找 Node 各型定義還是不好理解,要怎麼使用這些知識連結解題方法。所以我認為有圖解步驟輔助,會是比較容易理解的步驟。
以下解題方法來自網友與 GPT 提供的答案,我想在本文中嘗試自己做視覺化圖解,說明 CodeWars 5kyu - Can you get the loop ? 的解題思路。
node.getNext()
和 node.next
這兩個方法走入下一個節點。先前我一直很糾結於上圖,以為一定要找到環與鏈的交接處,再從倒數第一個環中的節點取得環的長度。看過別人的解答後,才脫離得先找到環的起始點這個想法。
鏈節初始狀態的可能性:有可能只有一個節,或是一條鏈卻沒有成環形。也可能有鏈有環,或是只有環型的狀況。我們不知道目前拿到的鏈結是什麼型態,所以我們要先可以拆解兩個理解的步驟:
Q1. 是否有環
Q2. 判斷環有多長
先有這個想像會比較容易理解後續。
就像是我們的時鐘,時針和分針的走路不一。如果這兩只針在走速不一的狀態下,仍有交疊處,就代表他們的行走路徑能成為一個環型。
如果還有點模糊,稍等一下,待會我們可以從下圖的示例 2、3 來驗證這個概念。
下圖是上面提到鏈節的幾種初始狀態可能,在使用長短針解法時的運行方式。
快針(紅色 F)
與 慢針(綠色 S)
,長短針一但走入環型範圍,就只會在環形內部環繞繼續行走。若無法前進則停止。慢針(綠色 S)
在第 2 步是可以站在節點上的。快針(紅色 F)
在第 1 步位置就已經超過慢針的第 1 步,並且當慢針
也抵達相同位置時,但快針
卻已經沒有下兩格可以前進所以止步。因為沒有環,所以環長為 0,0 是要返回的答案。慢針(綠色 S)
和 快針(紅色 F)
在第 3 步會在相同節點上相遇,3 即是我們要返回的答案。慢針(綠色 S)
和 快針(紅色 F)
在第 6 步會在相同節點上相遇。若環的長度再做調整,引用上述「長短針一但走入環型範圍,就只會在環形內部環繞繼續行走」的概念,快慢針可能會在走環狀第 n 圈的時候才相遇。總之只要有環就一定會相遇。(例如時鐘時針和分針一天會相遇 24 次)。延伸上面圖解的概念,可以以此來實作題目,先判斷是否有環,再取得環的長度。
node
。slow
,每次使用 getNext()
走 1 格節點。fast
,每次使用兩次的 getNext()
,共計走 2 格節點。return 0
。return 0
。while (fast && fast.getNext())
,如果有找到同值,兩針所處的位置就會停在交叉點上,然後跳入 Step 3 的步驟。fast
改為每次只走 1 格,當快針再次回到出發點(與慢針的交差點),就是環型的長度。function loop_size(node) {
//如果沒有節點,或是節點只有一個(也就是 node.getNext() 無法取值),則返回 0,因為一定無法成環形
if (!node || !node.getNext()) {
return 0;
}
/* Step 1 建立環形交集點 */
//如果有環形,可以用時鐘長短針的概念來看,先建立快針與慢針
let slow = node;
let fast = node;
/* Step 2 建立環形交集點 */
//當快針當前狀態能取值,並且快針下一格也存在,則迴圈成立
//慢針每次走一格,快針每次走兩格,如果快針和慢針得到同值,則提早離開迴圈
while (fast && fast.getNext()) {
slow = slow.getNext();
fast = fast.getNext().getNext();
if (slow === fast) {
break;
}
}
// 如果迴圈停止時,fast 和 slow 不相等
if (slow !== fast) {
return 0;
}
// Step 3: 固定兩針起始點為同一個點,將快針速度改為每次一格,回到原點的迴圈次數表環型長度
let count = 1;
fast = fast.getNext();
while (fast !== slow) {
fast = fast.getNext();
count++;
}
return count;
}