迭代 + 哨兵节点
解题思路
没引入 哨兵节点 之前，需要判断要删除的节点是不是头结点，还要判断节点是不是中间节点，代码比较冗余；
什么是 哨兵节点？
- 它是纯功能的，通常不保存任何数据；
- 其主要目的是使链表标准化，如 使链表永不为空、永不无头、简化插入和删除；
引入哨兵节点，无需再分步判断头节点和中间节点了，初始化虚拟头结点 dmy、curr 指向 head；
curr 不断后移一位，判断下一个节点的值是否等于 val；
- 找到了要删除的节点，则 curr 直接指向下下个节点，这样就删除了下一个节点；
- 否则 curr 继续向后移动；
最后返回 dmg.next 即可；
图解
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的长度，需要遍历链表一次； -
空间复杂度：
O(1)；
代码实现
var removeElements = function (head, val) {
let dmy = new ListNode(null, head);
let curr = dmy;
while (curr.next !== null) {
// 如果下一个节点的值等于 val，则删除下一个节点，否则指针向后移动
curr.next.val === val ? curr.next = curr.next.next : curr = curr.next;
}
return dmy.next;
};
尾递归
解题思路
递归：找到子问题；
对每个节点调用 removeElements 并在函数里根据节点 val 判断；
- 如果是 null 就返回 null；
- 如果是给定值就返回当前节点的下一个节点，不是则返回当前节点；
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的长度，递归过程中需要遍历链表一次； -
空间复杂度：
O(n)，其中 n 是链表的长度，空间复杂度主要取决于递归调用栈，最多不会超过 n 层；
代码实现
var removeElements = function (head, val) {
if (head === null) return head;
// 利用尾递归：返回「下一个节点」还是「下下一个节点」
head.next = removeElements(head.next, val);
// 是否返回下一个节点、还是当前节点
return head.val === val ? head.next : head;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 783. 二叉搜索树节点最小距离
上一篇
评论
