📘 題目敘述
給你一個單向鏈結串列的頭節點 head，請回傳這個鏈結串列的中間節點。
如果有兩個中間節點，請回傳第二個中間節點。
條件限制
- 串列中的節點數量在範圍
[1, 100] 1 <= Node.val <= 100
🧠 解題思路
我用快慢指標來找中間：
slow每次走一步fast每次走兩步
當 fast 走到尾端（或超過尾端）時，slow 剛好會走到中間。
而題目要求「偶數長度時回傳第二個中間」，其實這個 while 條件：
while (fast && fast->next)
就會自然讓 slow 停在第二個中間，所以不需要額外特判。
所有變數
fast：快指標，每次走兩步slow：慢指標，每次走一步
🪜 主要流程步驟
1. 初始化快慢指標都指向 head
我先把 fast 和 slow 都設成 head。
2. fast 走兩步、slow 走一步，直到 fast 不能再走兩步
只要 fast 還存在且 fast->next 存在，我就讓：
fast = fast->next->nextslow = slow->next
3. while 結束時 slow 就是答案
- 串列長度是奇數：
slow在唯一中間 - 串列長度是偶數：
slow在第二個中間（符合題意）
回傳 slow 即可。
⏱️ 複雜度
- 時間複雜度：
O(n) - 空間複雜度：
O(1)
💻 程式碼實作
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
};
🔗 題目連結
https://leetcode.com/problems/middle-of-the-linked-list/