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

前言

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

思路分析

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

遍历链表，杂度删除节点

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

从链表头部通过遍历的杂度方式顺着指针进行查找发现节点9的指针指向节点10(需要删除的节点)获取节点10指针指向的节点13修改节点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]，进一步了解。

文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注

很赞哦!（4455）