Middle of the Linked List (Linked List) 876

question

• 給定一個單向鏈結串列，找到其中間節點並回傳。
• 如果有兩個中點（鏈結串列長度為偶數），則回傳第二個中點。
  Ex.
  1 -> 2 -> 3 -> 4 -> 5 → 回傳節點 3
  1 -> 2 -> 3 -> 4 -> 5 -> 6 → 回傳節點 4

thoughts

方法 1：快慢指針 (Two Pointers)（最常見）

• 設定 slow 和 fast 指針，都從頭節點出發。
• fast 每次走 2 步，slow 每次走 1 步。
• 當 fast 到達尾端 時，slow 剛好在中點。
• 如果長度是奇數：slow 停在正中間。
• 如果長度是偶數：slow 停在第二個中點（符合題目要求）。
• 時間複雜度：O(n)
• 空間複雜度：O(1)
  方法 2：遍歷 + 陣列存儲
• 遍歷整個鏈表，把所有節點存到陣列中。
• 用 size / 2 找出中間節點並回傳。
• 時間複雜度：O(n)
• 空間複雜度：O(n)
• cons: 需要額外空間，不如快慢指針高效
  方法 3：兩次遍歷
• 第一次遍歷，計算鏈表長度 n。
• 第二次遍歷，走 n/2 步，停下來就是中點。
• 時間複雜度：O(n)
• 空間複雜度：O(1)
• 比快慢指針多一次遍歷，不是最佳解

summary

為什麼快慢指針最好？
只需要一次遍歷，效率最高。
不用額外空間，比陣列法更省記憶體。
能自動解決偶數長度鏈表回傳「第二個中點」的需求。

Kotlin

class Solution {
    fun middleNode(head: ListNode?): ListNode? {
        var slow = head
        var fast = head
        while (fast?.next != null) {
            slow = slow?.next
            fast = fast.next?.next
        }
        return slow
    }
}

Follow-up

• 如果鏈結串列長度為偶數，應該回傳前一個中點還是後一個中點？（LeetCode 預設回傳後一個）
• 是否能在 一次遍歷 中解決？（快慢指針就是一次遍歷）
• 如何擴展成找到 1/3 點或 1/4 點？