剑指offer-76、删除链表的节点
题⽬描述给定单向链表的头指针和⼀个要删除的节点的值，定义⼀个函数删除该节点。返回删除后的链表的头节点。
[*]此题对⽐原题有改动
[*]题⽬保证链表中节点的值互不相同
[*]该题只会输出返回的链表和结果做对⽐，所以若使⽤ C 或 C++ 语⾔，你不需要 free 或 delete 被删除的节点
数据范围:
<ul> 0 9 思路及解答
虚拟头节点
如果要删除链表⾥⾯的⼀个节点，其实就是将前置节点的next 直接指向当前节点的后置节点，这样在链表中再也找不到该节点了，也就是相当于删除了。
假设有⼀个链表，我们需要删除⾥⾯的 5 :
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231330111.png
⾸先需要判断链表头结点是不是为空，如果为空，那么就直接返回NULL ，如果等于我们要找的，那么直接返回下⼀个节点引⽤即可。
如果不符合以上说的，那么我们需要新建⼀个前置节点pre ,与现在的链表连接在⼀起：
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231330139.png
然后初始化⼀个 cur 节点表示当前节点，指向 head 节点：
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231330133.png
cur 不为空， cur 和 pre 后移：
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231331982.png
发现 cur 正是我们需要查找的 5 ，那么记录下 5 的下⼀个节点 1 ,也就是next :
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231331572.png
cur 的 next 指向 NULL ,使⽤ pre 的 next 指向刚刚记录的 next :
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231332010.png
简化链表也就是：
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231332195.png
取之前虚拟的头结点的后⼀个节点，就是删除掉之后的新链表：
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231332191.png
class ListNode { int val; ListNode next = null; public ListNode(int val) { this.val = val; } }public class Solution13 { public ListNode deleteNode(ListNode head, int val) { if (head == null) { return null; } if (head.val == val) { return head.next; } // ⽤⼀个节点将头结点链接起来 ListNode pre = new ListNode(-1); pre.next = head; ListNode cur = head; ListNode next = null; while (cur != null) { if (cur.val == val) { // 将前置节点直接连接后⼀个节点，相当于删除掉了该节点 pre.next = cur.next; break; } cur = cur.next; pre = pre.next; } return head; } } 迭代
通过遍历链表找到目标节点并修改指针，维护前驱指针，当找到目标节点时修改指针跳过该节点
public class Solution { public ListNode deleteNode(ListNode head, int val) { // 处理头节点就是要删除的节点的情况 if (head != null && head.val == val) { return head.next; } ListNode prev = null; ListNode curr = head; // 遍历查找目标节点 while (curr != null && curr.val != val) { prev = curr; curr = curr.next; } // 找到目标节点后跳过它 if (curr != null) { prev.next = curr.next; } return head; } }
[*]时间复杂度：O(n)，最坏情况下需要遍历整个链表
[*]空间复杂度：O(1)，只使用常数空间
递归
当前节点是要删除的节点则返回next，否则递归处理剩余链表
public class Solution { public ListNode deleteNode(ListNode head, int val) { // 递归终止条件 if (head == null) { return null; } // 当前节点是要删除的节点 if (head.val == val) { return head.next; } // 递归处理剩余链表 head.next = deleteNode(head.next, val); return head; } }
[*]时间复杂度：O(n)，需要处理每个节点
[*]空间复杂度：O(n)，递归调用栈的深度
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 感谢分享，学习下。 感谢，下载保存了 东西不错很实用谢谢分享 用心讨论，共获提升！ 分享、互助 让互联网精神温暖你我 收藏一下 不知道什么时候能用到 前排留名，哈哈哈
页:
[1]