LeetCode 解題筆記：2095. Delete the Middle Node of a Linked List

作者：王一哲
日期：2026年6月15日


LeetCode 題目連結：2095. Delete the Middle Node of a Linked List

解題想法

中等難度題目。建一個走訪用的虛擬節點 dummy 並指向 head，用 while 迴圈掃過鏈結串列一輪計算節點數量 n。接下來先排除 n = 1 的特例，直接回傳 None 或 nullptr。接下來處理一般狀況，要刪除的目標節點索引值為 $mid = \lfloor n/2 \rfloor$。如果用 Python 解題可以將 dummy 重新指向 head，如果用 C++ 解題則再建一個走訪用的虛擬節點 newDummy 並指向 head，用一個 for 迴圈將 dummy 或 newDummy 往下走 $mid - 1$ 次。如果此時 dummy.next.next != None 或 newDummy->next->next != nullptr，將 dummy.next 指向 dummy.next.next 或是將 newDummy->next->next 指向 newDummy->next；反之，將 dummy.next 指向 None 或是將 newDummy->next->next 指向 nullptr。最後回傳 head。由於這個寫法要掃過整個鏈結串列 1.5 次，速度偏慢。

討論區有一個厲害的寫法，建兩個走訪用的虛擬節點 fast 及 slow，fast 從 head.next.next 開始一次走兩格、slow 從 head 開始一次走一格，當 fast 走到底時，slow 正好走到要被刪除的節點前一格，只要將 slow.next 指向 slow.next.next 即可。

Python 程式碼

Runtime: 105 ms, beats 29.69%. Memory: 61.93 MB, beats 98.82%.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 先掃過鏈結串列一次計算節點數量
        dummy = ListNode()
        dummy = head
        n = 0
        while dummy:
            n += 1
            dummy = dummy.next
        
        # 特例，只有一個節點，回傳 None
        if n == 1: return None
        
        # 一般狀況，要刪除索引值 mid 的節點
        mid = n // 2
        dummy = head
        # 向下走 mid - 1 次
        for _ in range(mid - 1):
            dummy = dummy.next
        # 如果有 dummy.next.next，將 dummy.next 設定成 dummy.next.next
        if dummy.next.next:
            dummy.next = dummy.next.next
        else:  # 反之，設定為 None
            dummy.next = None
        
        # 回傳 head
        return head

非原創的快速解法。Runtime: 92 ms, beats 53.17%. Memory: 62.32 MB, beats 49.97%.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 特例，只有一個節點，回傳 None
        if not head.next: return None

        # fast 從 head.next.next 開始 一次走兩格，slow 從 head 開始一次走一格
        slow = head
        fast = head.next.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 將 slow.next 指向 slow.next.next
        slow.next = slow.next.next
        # 回傳 head
        return head

C++ 程式碼

Runtime: 11 ms, beats 8.52%. Memory: 312.08 MB, beats 54.78%.

/**
 * 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) {
        // 先掃過鏈結串列一次計算節點數量
        ListNode* dummy = head;
        int n = 0;
        while(dummy != nullptr) {
            n++;
            dummy = dummy->next;
        }
        
        // 特例，只有一個節點，回傳 nullptr
        if (n == 1) return nullptr;
        
        // 一般狀況，要刪除索引值 mid 的節點
        int mid = n / 2;
        ListNode* newDummy = head;
        // 向下走 mid - 1 次
        for(int i = 0; i < mid - 1; i++) {
            newDummy = newDummy->next;
        }
        // 如果有 newDummy->next->next，將 newDummy->next 設定成 newDummy->next->next
        if (newDummy->next->next != nullptr) {
            newDummy->next = newDummy->next->next;
        } else {  // 反之，設定為 nullptr
            newDummy->next = nullptr;
        }
        // 回傳 head
        return head;
    }
};

非原創的快速解法。Runtime: 2 ms, beats 49.39%. Memory: 312.08 MB, beats 54.78%.

/**
 * 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) {
        // 特例，只有一個節點，回傳 nullptr
        if (head->next == nullptr) return nullptr;
        
        // fast 從 head->next->next 開始 一次走兩格，slow 從 head 開始一次走一格
        ListNode* fast = head->next->next;
        ListNode* slow = head;
        while(fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        
        // 將 slow->next 指向 slow->next->next
        slow->next = slow->next->next;
        // 回傳 head
        return head;
    }
};