剑指 Offer 18. 删除链表的节点 - leetcode 剑指offer系列

题目难度: 简单

原题链接

今天继续更新剑指 offer 系列, 这道题是比较基础的链表问题, 适合入门同学. 这里同样提供多种方案还有进阶问题供大家参考~

老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了

题目描述

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

题目保证链表中节点的值互不相同

若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

题目样例

示例

输入

head = [4,5,1,9], val = 5

输出

[4,1,9]

解释

给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

题目思考

(思考题答案在最后)

进阶问题: 如果节点的值存在重复需要怎么做?

解决方案

思路

分析

要想删除链表中的节点, 我们必须知道它的前一个节点, 然后将其前一个节点的 next 值指向当前节点的 next 即可所以直接使用两个指针, 一个保存前一个节点 pre, 一个保存当前节点 cur, 遇到当前节点值是输入值的时候按照上面做法删除即可. (大多数链表问题都可以先尝试使用多个指针的方案, 画图模拟整个过程更容易理解)注意题目中节点没有重复, 所以删除之后直接跳出循环即可这里提供两种实现方案, 一种更好理解, 一种代码更简短, 具体见下面的实现和代码部分

实现

方案 1: 特殊处理 head, 如果删除值是 head 直接返回 head;否则把 head 作为第一个 pre, head.next 作为第一个 cur, 依次遍历找删除节点 方案 2: 增加一个哨兵节点 prehead, 其 next 值是原始 head然后把 prehead 作为 pre, head 作为第一个 cur, 这样就不需要特殊处理 head 了, 把它当成普通节点处理即可最后返回 prehead.next 就是新的 head

复杂度

时间复杂度 O(N) 最差情况需要遍历整个链表的所有节点 空间复杂度 O(1) 只使用了几个变量

代码

方案 1 - 特殊处理 head

class Solution: def deleteNode(self, head: ListNode, val: int) -> ListNode: # 需要考虑head不存在或者删除节点就是head的情况 if not head: return head if head.val == val: return head.next pre = head cur = head.next while cur: if cur.val == val: # 找到删除节点了, 直接将pre的next指向cur的next就完成删除操作 pre.next = cur.next break # 更新pre和cur, 依次后移一个节点 pre = cur cur = cur.next return head

方案 2 - 增加哨兵节点

class Solution: def deleteNode(self, head: ListNode, val: int) -> ListNode: prehead = ListNode(0) prehead.next = head cur, pre = head, prehead while cur: if cur.val == val: # 找到删除节点了, 直接将pre的next指向cur的next就完成删除操作 pre.next = cur.next break # 更新pre和cur, 依次后移一个节点 pre = cur cur = cur.next return prehead.next

思考题答案

进阶问题: 如果节点的值存在重复需要怎么做?

对方案 2 稍加改造即可: 找到删除节点后不跳出循环, 而是在更新 pre 的 next 之后, 保持 pre 不变 (因为有可能存在连续多个待删除节点, 这样保持 pre 不变才能将其指向要一个不会被删除的节点), 而将 cur 继续后移; 而没找到时再移动 pre 和 cur由于两个条件都需要后移cur, 所以可以将其提取到 if 条件之外, 简化代码这道题也即203. 移除链表元素, 具体代码如下: class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: prehead = ListNode(0) prehead.next = head cur, pre = head, prehead while cur: if cur.val == val: # 找到删除节点了, 直接将pre的next指向cur的next就完成删除操作 pre.next = cur.next else: # 当前cur不是要删除节点, 更新pre, 后移一个节点 pre = cur # 由于两个条件都需要后移cur, 这里可以将其提取出来 cur = cur.next return prehead.next

---

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的

我的 Leetcode

我的牛客网博客

我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊