前言

有一個單向鏈表，給定了頭指針和一個節點指針，如何在O(1)的時間內刪除該節點?本文將分享一種實現思路來解決這個問題，歡迎各位感興趣的開發者閱讀本文。

思路分析

在單向鏈表中，要想刪除一個節點，首先想到的做法就是：從鏈表的頭節點開始，按照順序遍歷查找要刪除的節點，找到后改變指針指向即可完成節點刪除。

遍歷鏈表，刪除節點

接下來，我們舉個鏈表的例子，刪除 節點10 ，那么刪除過程就如下圖所示：

1. 從鏈表頭部通過遍歷的方式順著指針進行查找
2. 發現節點9的指針指向節點10(需要刪除的節點)
3. 獲取節點10指針指向的節點13
4. 修改節點9的指針指向，將其指向節點13，就完成了節點10的刪除

通過這種方式，我們的確刪除了給定的節點，但是需要從頭開始遍歷鏈表尋找節點，時間復雜度是O(n)。不滿足題目要求，這種方式不可行。

覆蓋節點，實現刪除

接下來，我們換一種思路，既然最耗時的地方是遍歷尋找節點，那么我們就不遍歷了，充分利用題目所給條件來進一步思考。

再次審題后，我們發現它給出了要刪除節點的指針，那么我們就可以拿到其指針所指向的值，有了這個值，我們就可以：

• 將待刪除節點值的進行覆蓋
• 修改指針指向，刪除其下一個節點

我們繼續用上個章節所舉的例子，它的執行過程如下圖所示：

注意：待刪除節點的下一個節點值是最后一個時，我們只需將待刪除節點的指針指向null即可。

如果其下一個節點之后還有節點，那我們只需要獲取那個節點，將其指針指向獲取到的節點即可，如下圖所示：

image-20220210213628642

通過上述思路我們在O(1)的時間內刪除了給定節點，但是還有一個問題：如果要刪除的節點位于鏈表的尾部，那么它就沒有下一個節點，此時我們就不能用這個辦法了，只能順序遍歷得到該節點的前序節點，并完成刪除操作。

時間復雜度分析：對于n-1個非尾節點而言，我們可以在O(1)的時間內利用節點覆蓋法實現刪除，但是對于尾節點而言，我們仍然需要按序遍歷來刪除節點，時間復雜度是O(n)。那么，總的時間復雜度就為：[(n-1) * O(1) + O(n)] / n，最終結果還是 O(1)，符合題目要求。

如果鏈表中只有一個節點，而我們又要刪除鏈表的頭節點(也是尾節點)，那么，此時我們在刪除節點之后還需要把鏈表的頭節點設置為null。

實現代碼

有了思路之后，我們就能愉快的寫出代碼了，如下所示：

• 鏈表中只有1個節點時，直接返回nul，調用者刪除鏈表的頭部節點即可
• 待刪除節點無下一個節點時，則按序遍歷尋找到其上一個節點，將指針指向null即可
• 使用覆蓋節點法，完成節點的刪除

type ListNode = { element: number; next: ListNode | null };

export class DeleteLinkedListNode {
  deleteNode(listHead: ListNode, toBeDeleted: ListNode): ListNode | null {
    // 鏈表中只有一個節點時，返回null
    if (listHead.next == null) {
      return null;
    }
    // 待刪除節點處于末尾時，則按順序遍歷節點實現刪除
    if (toBeDeleted.next == null) {
      let curNode = listHead.next;
      // 尋找待刪除節點的上一個節點
      while (
        curNode.next != null &&
        curNode.next.element !== toBeDeleted.element
      ) {
        curNode = curNode.next;
      }
      // 上一個節點已找到，將其指針指向null即可
      curNode.next = null;
      return listHead;
    }

    // 待刪除節點之后還有節點，則采取覆蓋法以達到刪除的目的
    // 待刪除節點的值改為其下一個節點的值
    toBeDeleted.element = toBeDeleted.next.element;
    // 待刪除節點的指針指向待刪除節點的下下個節點
    toBeDeleted.next = toBeDeleted.next.next;
    return listHead;
  }
}

測試用例

最后，我們用上個章節所舉的例子來驗證下代碼是否能正確執行。

import { DeleteLinkedListNode } from "../DeleteLinkedListNode.ts";
import LinkedList from "../lib/LinkedList.ts";

const listNode = new LinkedList();
listNode.push(3);
listNode.push(5);
listNode.push(7);
listNode.push(9);
listNode.push(10);
listNode.push(13);
listNode.push(15);

const deleteLinkedListNode = new DeleteLinkedListNode();
// 獲取鏈表頭指針與節點10的指針
const result = deleteLinkedListNode.deleteNode(
  listNode.getHead(),
  listNode.getElementAt(4)
);
if (result == null) {
  // 刪除鏈表的頭節點
  listNode.removeAt(0);
}
console.log("刪除節點10后，鏈表的剩余節點為：", listNode.toString());

運行結果如下所示：

上述代碼中的LinkedList類是自己實現的，對此感興趣的開發者請移步：鏈表與變相鏈表的實現[1]。

示例代碼

本文實例的完整代碼如下：

• DeleteLinkedListNode.ts[2]
• deleteLinkedListNode-test.ts[3]
• LinkedList.ts[4]

寫在最后

至此，文章就分享完畢了。

我是神奇的程序員，一位前端開發工程師。

如果你對我感興趣，請移步我的個人網站[5]，進一步了解。

• 文中如有錯誤，歡迎在評論區指正，如果這篇文章幫到了你，歡迎點贊和關注??
• 文中鏈接可從文末參考資料中獲取

參考資料

[1]鏈表與變相鏈表的實現: https://juejin.cn/post/6844904176229548039

[2]DeleteLinkedListNode.ts: https://github.com/likaia/algorithm-practice/blob/04791ec8b301c78d195e1d638e2b8260c53d7c69/src/DeleteLinkedListNode.ts#L3

[3]deleteLinkedListNode-test.ts: https://github.com/likaia/algorithm-practice/blob/04791ec8b301c78d195e1d638e2b8260c53d7c69/src/test-case/deleteLinkedListNode-test.ts#L4

[4]LinkedList.ts: https://github.com/likaia/algorithm-practice/blob/212a5351f662ddf48bab2c289194bb09c378d9a1/src/lib/LinkedList.ts#L9

[5]個人網站: https://www.kaisir.cn/