前言

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

思路分析

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

遍歷鏈表，刪除節(jié)點

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

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

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

覆蓋節(jié)點，實現(xiàn)刪除

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

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

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

我們繼續(xù)用上個章節(jié)所舉的例子，它的執(zhí)行過程如下圖所示：

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

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

image-20220210213628642

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

時間復雜度分析：對于n-1個非尾節(jié)點而言，我們可以在O(1)的時間內(nèi)利用節(jié)點覆蓋法實現(xiàn)刪除，但是對于尾節(jié)點而言，我們?nèi)匀恍枰葱虮闅v來刪除節(jié)點，時間復雜度是O(n)。那么，總的時間復雜度就為：[(n-1) * O(1) + O(n)] / n，最終結果還是 O(1)，符合題目要求。

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

實現(xiàn)代碼

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

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

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

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

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

測試用例

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

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();
// 獲取鏈表頭指針與節(jié)點10的指針
const result = deleteLinkedListNode.deleteNode(
  listNode.getHead(),
  listNode.getElementAt(4)
);
if (result == null) {
  // 刪除鏈表的頭節(jié)點
  listNode.removeAt(0);
}
console.log("刪除節(jié)點10后，鏈表的剩余節(jié)點為：", listNode.toString());

運行結果如下所示：

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

示例代碼

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

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

寫在最后

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

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

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

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

參考資料

[1]鏈表與變相鏈表的實現(xiàn): 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]個人網(wǎng)站: https://www.kaisir.cn/