用O(1)的时间复杂度删除链表节点

前言

有一个单向链表，给定了头指针和一个节点指针，如何在O(1)的时间内删除该节点？本文将分享一种实现思路来解决这个问题，欢迎各位感兴趣的开发者阅读本文。

思路分析

在单向链表中，要想删除一个节点，首先想到的做法就是：从链表的头节点开始，按照顺序遍历查找要删除的节点，找到后改变指针指向即可完成节点删除。

遍历链表，删除节点

接下来，我们举个链表的例子，删除 节点10 ，那么删除过程就如下图所示：

• 从链表头部通过遍历的方式顺着指针进行查找
• 发现节点9的指针指向节点10（需要删除的节点）
• 获取节点10指针指向的节点13
• 修改节点9的指针指向，将其指向节点13，就完成了节点10的删除

image-20220209222408426

通过这种方式，我们的确删除了给定的节点，但是需要从头开始遍历链表寻找节点，时间复杂度是O(n)。不满足题目要求，这种方式不可行。

覆盖节点，实现删除

接下来，我们换一种思路，既然最耗时的地方是遍历寻找节点，那么我们就不遍历了，充分利用题目所给条件来进一步思考。

再次审题后，我们发现它给出了要删除节点的指针，那么我们就可以拿到其指针所指向的值，有了这个值，我们就可以：

• 将待删除节点值的进行覆盖
• 修改指针指向，删除其下一个节点

我们继续用上个章节所举的例子，它的执行过程如下图所示：

image-20220209232658888

注意：待删除节点的下一个节点值是最后一个时，我们只需将待删除节点的指针指向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());

运行结果如下所示：

image-20220213155754474

上述代码中的LinkedList类是自己实现的，对此感兴趣的开发者请移步：链表与变相链表的实现[1]。

示例代码

本文实例的完整代码如下：

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

写在最后

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

我是神奇的程序员，一位前端开发工程师。

参考资料

[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/