您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

LeetCode 237. 刪除鏈表中的節點：僅給節點指針 O(1) 技巧解法

編輯：關於C語言

LeetCode 237. 刪除鏈表中的節點：僅給節點指針 O(1) 技巧解法

經典面試題：給定單鏈表中**非尾節點**的指針 `node`，在**無法訪問頭指針**情況下刪除該節點。本文揭示「值覆蓋 + 刪除下一節點」的 O(1) 時間 O(1) 空間核心技巧，並分析適用條件與局限。

題目約束與核心難點

輸入：待刪除節點指針 `node`（保證非尾節點）。
限制：無法訪問鏈表頭指針 `head`，無法訪問前驅節點。
目標：刪除 `node` 所指節點，鏈表結構保持正確。
示例：1→2→3→4，給節點 3 → 變為 1→2→4。

常規刪除需前驅節點 `pre->next = node->next`，但無 `head` 無法獲取 `pre`。

核心技巧：偷梁換柱

**將下一節點的值複製到當前節點，然後刪除下一節點。**

node->val = node->next->val;      // 1. 覆蓋值
node->next = node->next->next;    // 2. 跳過下一節點（邏輯刪除）
// 可選：free(node->next) 釋放內存

效果：邏輯上「當前節點」消失了，實際上是「下一節點」被移除，但數據值保留了下來。

C 語言實現

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) {
    // 題目保證 node 非空且非尾節點，但防禦性檢查無妨
    if (node == NULL || node->next == NULL) return;

    struct ListNode *nextNode = node->next;
    node->val = nextNode->val;       // 複製數據
    node->next = nextNode->next;     // 旁路下一節點
    free(nextNode);                  // 釋放被旁路節點內存（工程必須）
}

為什麼這行得通？

鏈表節點由「值」和「指向下一節點的指針」組成。
外部觀察者只能通過 `head` 遍歷訪問節點值序列。
將節點 A 的值替為節點 B 的值，並讓 A 指向 B 的下一節點，外部遍歷結果等價於「節點 A 被移除，節點 B 取代了 A 的位置」。
實際被釋放的是節點 B 的內存，但邏輯上達到了「刪除節點 A」的效果。

關鍵限制：不能刪除尾節點

若 `node` 是尾節點，`node->next == NULL`，無法獲取下一節點值與指針，技巧失效。題目明確保證「非尾節點」。

適用場景與不適用場景

場景	是否適用	說明
單鏈表，給非尾節點指針，無頭指針	✅ 完美	本題標準解
雙向鏈表	❌ 不需要	有 `prev` 指針，常規刪除即可
需釋放節點關聯資源（如文件句柄、鎖）	⚠️ 謹慎	實際釋放的是下一節點，資源清理邏輯可能錯位
外部持有該節點指針的其他引用	❌ 危險	外部引用指向的節點內容被竄改，指針指向下一節點
循環鏈表	✅ 適用	邏輯相同，尾節點有下一節點

測試驗證

// 構建 1→2→3→4
ListNode *n1=create(1), *n2=create(2), *n3=create(3), *n4=create(4);
n1->next=n2; n2->next=n3; n3->next=n4;

deleteNode(n3); // 刪除節點 3
// 遍歷輸出：1 2 4
// 內存：n3 被 free，n4 存活（值 4 保留在原 n3 位置）