2095. Delete the Middle Node of a Linked List

📘 題目敘述

給你一個 linked list 的頭節點 head。請刪除中間節點，並回傳修改後 linked list 的頭節點 head。

一個大小為 n 的 linked list，其中間節點定義為：從頭開始、以 0-based index 計算的第 ⌊n / 2⌋ 個節點，其中 ⌊x⌋ 表示小於或等於 x 的最大整數（floor）。

• 當 n = 1, 2, 3, 4, 5 時，中間節點的 index 分別是 0, 1, 1, 2, 2。

條件限制

• linked list 的節點數量在範圍 [1, 10^5]。
• 1 <= Node.val <= 10^5。

🧠 解題思路

我的做法是「先數長度，再定位要刪的位置」。

• 題目定義中間節點 index 是 ⌊n/2⌋，所以我先掃一次把長度 n 算出來，並令 count = n/2。
• 接著要刪掉 index = count 的節點。刪節點需要「前一個節點」才能改指標，所以我用指標 q 走到 index = count - 1 的位置，讓 q->next 剛好是要刪的中間節點。
• 最後用 q->next = (q->next)->next; 把中間節點跳過即可。

另外我先處理長度很小的情況：

• 若 head 是空或只有一個節點（!head || !(head->next)），刪掉中間節點後會變成空串列，所以回傳 nullptr。

所有變數

• head：輸入 linked list 的頭節點指標，也是最後要回傳的頭
• count：先拿來記錄節點總數，後來改成 n/2（中間節點的 index）
• p：用來走訪整條 linked list 計算長度的指標
• q：用來走到「中間節點前一格」的指標，方便修改 next

🪜 主要流程步驟

1. 特例：長度 1 的 linked list

• 如果 head 不存在，或 head->next 不存在：
• • 代表節點數是 0 或 1
  • 刪掉中間節點後會是空串列
  • 直接回傳 nullptr

2. 第一次掃描：計算總長度 n

• 用 p 從 head 走到 nullptr
• 每走一步 count++
• 掃完後 count 就是 n

3. 算出中間節點的 index

• count /= 2
• 此時 count 就是題目要刪的 index：⌊n/2⌋

4. 第二次掃描：讓 q 走到中間節點的前一個節點

• q 從 head 出發
• 走 count - 1 步後：
• • q 會在 index = count - 1
  • q->next 會在 index = count（也就是要刪的中間節點）

5. 刪掉中間節點（跳過它）

• q->next = (q->next)->next;
• 回傳 head

💻 程式碼實作

/**
 * 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* deleteMiddle(ListNode* head) {
        if (!head || !(head->next)) {
            return nullptr;
        }
        int count = 0;
        for (ListNode* p = head; p; p = p->next) {
            count++;
        }
        count /= 2;
        ListNode* q = head;
        for (int i = 0; i < count - 1; i++) {
            q = q->next;
        }
        q->next = (q->next)->next;
        return head;
    }
};

🔗 題目連結

https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/