題目 876：「鏈結串列的中間節點 (Middle of the Linked List)」要求我們找出單向鏈結串列的中間節點。如果有兩個中間節點，則回傳第二個中間節點。這題考驗我們對鏈結串列遍歷的掌握能力，特別是如何高效地定位鏈結串列的中點。

題目：

給定一個單向鏈結串列，找到並回傳它的中間節點。如果鏈結串列中節點的數量是偶數，那麼回傳第二個中間節點。

範例：

1. 輸入：head = [1,2,3,4,5]

   • 輸出：節點值為 3
   • 解釋：中間節點是值為 3 的節點。

2. 輸入：head = [1,2,3,4,5,6]

   • 輸出：節點值為 4
   • 解釋：中間有兩個節點，3 和 4，回傳第二個節點。

解題思路

使用快慢指標，每次快指標走兩步，而慢指標走一步，這樣快指標走到終點時，慢指標剛好就走到鍊結串列的中間節點，然後在處理奇偶數節點的問題。

實作：

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        // 快指標每次走兩步，慢指標每次走一步
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 當快指標走到終點時，慢指標即為中間節點
        return slow;
    }
};

參考：
#876. Middle of the Linked List