題目描述:給定一個單向鏈結串列的頭節點 head,回傳串列的中間節點。若串列有兩個中間節點(偶數長度),則回傳第二個中間節點。
解題思路:使用 快慢指標(Floyd's Tortoise and Hare) 技巧,在單次遍歷中找到中點。
slow 每次移動一步,fast 每次移動兩步。fast 到達串列末尾(fast == nullptr 或 fast->next == nullptr)時,slow 恰好位於中間位置。為何這樣有效?當 fast 走了 2k 步時,slow 走了 k 步,恰好是總長度的一半。
邊界條件分析(決定迴圈終止條件):
終止條件 fast != nullptr && fast->next != nullptr 可同時正確處理兩種情況。
時間複雜度:O(n) — fast 指標每次移動兩步,整個迴圈執行 ⌊n/2⌋ 次,為線性時間(n 為鏈結串列的節點數)。
空間複雜度:O(1) — 只使用兩個指標變數,不需要任何與輸入大小相關的額外空間。
1. Initialize slow = head, fast = head. 2. While fast is not null AND fast.next is not null: a. slow = slow.next b. fast = fast.next.next 3. Return slow.
兩次遍歷 O(n):第一次遍歷計算串列總長度 n,第二次遍歷走到第 ⌊n/2⌋ 個節點並回傳。邏輯直觀,但需要遍歷兩次;快慢指標法只需一次遍歷且空間相同,通常更受面試官青睞。
轉存至陣列 O(n):遍歷串列將所有節點存入 vector<ListNode*>,直接回傳 nodes[nodes.size() / 2]。實作最簡單,但需要 O(n) 的額外空間。適合快速驗證答案,不適合作為最終解法。
fast != nullptr && fast->next != nullptr 與 fast->next != nullptr && fast->next->next != nullptr 分別對應哪種中間節點的定義(第一個還是第二個)?請用偶數長度串列驗證。