【解題筆記 - JS】Node 找到循環鍊的長度

Node 對我來說一直是很似懂非懂的概念，題型有樹狀、鏈節等。因為沒有實際可見的數字或字串等實物可以觀察中間步驟，所以比起其他解題抽象許多。如果光是查找 Node 各型定義還是不好理解，要怎麼使用這些知識連結解題方法。所以我認為有圖解步驟輔助，會是比較容易理解的步驟。

題目資訊

• 題目來源：https://www.codewars.com/kata/52a89c2ea8ddc5547a000863
• 題目說明：
  給您一個作為鍊錶開頭的節點。此清單包含一個懸掛塊和一個循環。您的目標是確定循環的長度。您可以使用 node.getNext() 和 node.next 這兩個方法走入下一個節點。
  ※ 環長就是下圖中紫色的區塊

原始題目

先前我一直很糾結於上圖，以為一定要找到環與鏈的交接處，再從倒數第一個環中的節點取得環的長度。看過別人的解答後，才脫離得先找到環的起始點這個想法。

解題思路

建立鏈節概念

鏈節初始狀態的可能性：有可能只有一個節，或是一條鏈卻沒有成環形。也可能有鏈有環，或是只有環型的狀況。我們不知道目前拿到的鏈結是什麼型態，所以我們要先可以拆解兩個理解的步驟：
Q1. 是否有環
Q2. 判斷環有多長
先有這個想像會比較容易理解後續。

鏈的可能性

常見的長短針解法

Q1. 長短針解法：理解「是否有環」的概念

就像是我們的時鐘，時針和分針的走路不一。如果這兩只針在走速不一的狀態下，仍有交疊處，就代表他們的行走路徑能成為一個環型。

如果還有點模糊，稍等一下，待會我們可以從下圖的示例 2、3 來驗證這個概念。

Q2. 視覺化長短針解法：環的長度

下圖是上面提到鏈節的幾種初始狀態可能，在使用長短針解法時的運行方式。

1. 假設有兩只針，快針（紅色 F）與 慢針（綠色 S），長短針一但走入環型範圍，就只會在環形內部環繞繼續行走。若無法前進則停止。
   - 快針：每次走 2 個節點。
   - 慢針：每次走 1 個節點。
   - 數字標示：第 n 步。
   - 橘黃色圈圈：兩只針在環繞環形多次後的交疊處。
2. 示例 2：有以上概念後，我們可以從示例 2 回推先前提到「如果這兩只針在走速不一的狀態下，仍有交疊處，就代表他們的行走路徑能成為一個環型」這句話。
   當只有鏈沒有環的狀態下，兩針走到無法再行進下一步時就會停止。
   - 慢針（綠色 S）在第 2 步是可以站在節點上的。
   - 快針（紅色 F）在第 1 步位置就已經超過慢針的第 1 步，並且當慢針也抵達相同位置時，但快針卻已經沒有下兩格可以前進所以止步。因為沒有環，所以環長為 0，0 是要返回的答案。
3. 示例 3：假設題目給我們的是有鏈也有環的鏈結。
   - 慢針（綠色 S） 和 快針（紅色 F）在第 3 步會在相同節點上相遇，3 即是我們要返回的答案。
4. 示例 4：示例 4 中，慢針（綠色 S） 和 快針（紅色 F）在第 6 步會在相同節點上相遇。若環的長度再做調整，引用上述「長短針一但走入環型範圍，就只會在環形內部環繞繼續行走」的概念，快慢針可能會在走環狀第 n 圈的時候才相遇。總之只要有環就一定會相遇。（例如時鐘時針和分針一天會相遇 24 次）。

長短針解法

解題程式碼

延伸上面圖解的概念，可以以此來實作題目，先判斷是否有環，再取得環的長度。

1. 設定快慢針

• 起始點為 node。
• 慢針：slow，每次使用 getNext() 走 1 格節點。
• 快針：fast，每次使用兩次的 getNext() ，共計走 2 格節點。

2. 判斷是否有環

• 帶入情境，如果沒有節點，或無法前進，直接 return 0。
• 每次移動，都判斷兩針所處位置是否同值。若兩針跑完迴圈始終不相等，也 return 0。
• 如果兩針有同值，代表這是一個有環的鏈表。讓我們進入「取得環的長度」的步驟。

3. 取得環的長度

• Step 2 中的 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;
}

延伸

• 其他解法：https://github.com/soonlive/codewars/issues/1
• 鏈表題型變化：http://www.heartthinkdo.com/?p=3308