---
title: "876. Middle of the Linked List"
url: "https://laigary.com/interview/coding/876-middle-of-the-linked-list"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Linked List", "Two Pointers"]
---

# 876. Middle of the Linked List

[876\. Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)

回傳鏈結串列的中間節點。**節點數是偶數時，回傳後面那一個**。

## 思路

鏈結串列沒有 `len()`，也不能用索引 —— 這就是這題的全部難點。

### 直覺解：數兩趟

先走一趟數出長度 `n`，再走 `n // 2` 步。一定寫得出來，而且很好解釋。缺點是走了兩趟。

### 一趟解：快慢指針

要一趟做完，關鍵是**用相對速度取代絕對位置**：

> 讓 `fast` 一次走兩步、`slow` 一次走一步。`fast` 走到底時，它走的距離是 `slow` 的兩倍 —— 所以 `slow` 剛好在一半的地方。

這個「兩倍速」的想法是鏈結串列題最重要的工具之一，因為串列不能隨機存取，**唯一能拿到「相對位置」的方法就是讓兩個指針用不同的速度或起點走**。

偶數長度時要回傳後面那個中點，這個版本剛好自動符合，不用特別處理 —— 下面解釋為什麼。

## 解題方向

### 數兩趟

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        count = 1
        while curr.next != None:
            curr = curr.next
            count += 1
        
        res = head
        count = count // 2
        while count > 0:
            count -= 1
            res = res.next

        return res
```

`count` 從 1 開始（把 `head` 自己算進去），所以迴圈條件是 `curr.next != None` 而不是 `curr != None`。這種「從 1 開始數、看下一個」的寫法很容易差一，如果不確定就從 0 開始、條件用 `while curr`，比較不會錯。

這版在 `head` 是 `None` 時會 `AttributeError`。LeetCode 保證至少 1 個節點所以不會踩到，但面試時可以主動提一句。

### 快慢指針

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow
```

**為什麼偶數長度時剛好回傳後面那個中點？** 因為迴圈條件是 `while fast and fast.next`：

- 長度 5（奇數）：`fast` 走到最後一顆時 `fast.next` 是 `None`，停下來，`slow` 在索引 2 —— 正中間。
- 長度 6（偶數）：`fast` 走出串列變成 `None`，停下來，`slow` 在索引 3 —— 也就是**後面那個**中點。

如果題目要的是前面那個中點（例如 [143. Reorder List](/interview/coding/143-reorder-list) 需要把串列切兩半時），就把條件改成 `while fast.next and fast.next.next`。**這兩個條件的差別就是「回傳哪個中點」**，值得記住，因為切串列的題目對這個很敏感。

## 補充

**快慢指針的其他用途**：[141. Linked List Cycle](/interview/coding/141-linked-list-cycle)（有環時快的會追上慢的）、[143. Reorder List](/interview/coding/143-reorder-list)（先找中點再反轉後半）、[2095. Delete the Middle Node of a Linked List](/interview/coding/2095-delete-the-middle-node-of-a-linked-list)（要停在中點的**前一個**才能刪）、[19. Remove Nth Node From End of List](/interview/coding/19-remove-nth-node-from-end-of-list)（改成讓快的先走 n 步）。

共同點都是「**沒有索引，就用兩個指針的相對關係換出位置資訊**」，整理見 [Linked List 模板](/interview/coding/linked-list-template)。

## 複雜度

**數兩趟**
- 時間 $O(n)$ — 走兩趟，仍然是線性
- 空間 $O(1)$

**快慢指針**
- 時間 $O(n)$ — 只走一趟，`fast` 走 $n/2$ 次迴圈
- 空間 $O(1)$

其中 `n` 是節點數。兩者同級，快慢指針的好處是**一趟解決**，而且它是後面一整批串列題的基礎工具。