前言

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

思路分析

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

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

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

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

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

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

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

再次審題后，我們發(fā)現(xiàn)它給出了要?jiǎng)h除節(jié)點(diǎn)的指針，那么我們就可以拿到其指針?biāo)赶虻闹?，有了這個(gè)值，我們就可以：

• 將待刪除節(jié)點(diǎn)值的進(jìn)行覆蓋
• 修改指針指向，刪除其下一個(gè)節(jié)點(diǎn)

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

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

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

image-20220210213628642

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

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

如果鏈表中只有一個(gè)節(jié)點(diǎn)，而我們又要?jiǎng)h除鏈表的頭節(jié)點(diǎn)(也是尾節(jié)點(diǎn))，那么，此時(shí)我們?cè)趧h除節(jié)點(diǎn)之后還需要把鏈表的頭節(jié)點(diǎn)設(shè)置為null。

實(shí)現(xiàn)代碼

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

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

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

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

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

測(cè)試用例

最后，我們用上個(gè)章節(jié)所舉的例子來驗(yàn)證下代碼是否能正確執(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é)點(diǎn)10的指針
const result = deleteLinkedListNode.deleteNode(
  listNode.getHead(),
  listNode.getElementAt(4)
);
if (result == null) {
  // 刪除鏈表的頭節(jié)點(diǎn)
  listNode.removeAt(0);
}
console.log("刪除節(jié)點(diǎn)10后，鏈表的剩余節(jié)點(diǎn)為：", listNode.toString());

運(yùn)行結(jié)果如下所示：

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

示例代碼

本文實(shí)例的完整代碼如下：

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

寫在最后

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

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

如果你對(duì)我感興趣，請(qǐng)移步我的個(gè)人網(wǎng)站[5]，進(jìn)一步了解。

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

參考資料

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