文章目录加载中
快速删除链表节点
# 1. 题目描述
给定单向链表的头指针和一个结点指针,定义一个函数在 $O(1)$ 时间删除该结点。
# 2. 思路描述
正常的做法肯定是在 $O(N)$ 时间内删除节点。而这么过分的要求,显然是通过“重新赋值”才能做到。
比如要删除节点 a,那么就将 a.next 的 value 和 next 赋值给节点 a,然后删除 a.next。
表面“看起来”像是删除了节点 a,其实是将其后节点的信息转移到了它自己身上。
除此之外,对于最后一个节点,还是要退化成 $O(N)$ 的复杂度。而整体分析一下复杂度:
$$
O(T) = (O(N) + O(1) * (n - 1)) / n = O(1)
$$
# 3. 代码实现
class Node {
/**
* 节点构造函数
* @param {*} value
* @param {Node} next
*/
constructor(value, next) {
this.value = value;
this.next = next;
}
}
/**
*
* @param {Node} head
* @param {Node} toDelete
*/
function deleteNode(head, toDelete) {
if (head === toDelete || !toDelete || !head) {
return;
}
let nextNode = toDelete.next;
if (!nextNode) {
// 尾节点
let node = head;
while (node.next !== toDelete) {
node = node.next;
}
node.next = null;
toDelete = null;
} else {
toDelete.value = nextNode.value;
toDelete.next = nextNode.next;
nextNode = null;
}
}
/**
* 测试代码
*/
let node3 = new Node(3, null),
node2 = new Node(2, node3),
node1 = new Node(1, node2),
head = new Node(null, node1);
deleteNode(head, node2);
let node = head.next;
while (node) {
console.log(node.value);
node = node.next;
}
本文来自心谭博客:xin-tan.com,经常更新web和算法的文章笔记,前往github查看目录归纳:github.com/dongyuanxin/blog