思路分析
在单向链表中，要想删除一个节点，首先想到的做法就是：从链表的头节点开始，按照顺序遍历查找要删除的节点，找到后改变指针指向即可完成节点删除。
遍历链表，删除节点
接下来，我们举个链表的例子，删除 节点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]，进一步了解。
- 文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注😊
- 文中链接可从文末参考资料中获取
参考资料
[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/
