个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言前面我们学习了关于数组的算法题这一章节我们会学习关于链表算法题链表也是一种数据结构我会在这里介绍一些链表的基础知识以及如何操作链表。题目背景LeetCode 203题意删除链表中等于给定值 val 的所有节点。示例 1 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5]示例 2 输入head [], val 1 输出[]示例 3 输入head [7,7,7,7], val 7 输出[]题目分析关于这道题目我们第一个考虑的是前面在数组中常规用到的循环遍历但是这是完全行不通的因为数组和链表有本质的区别首先数组是通过索引直接访问和修改任意位置的而链表没有索引同时链表的删除需要知道前驱节点尤其是单向列表下面我会具体的介绍如何在链表中删除元素 。解法一/** * 方法1 * 时间复杂度 O(n) * 空间复杂度 O(1) * param head * param val * return */ public ListNode removeElements(ListNode head, int val) { while(head!null head.valval) { head head.next; } ListNode curr head; while(curr!null curr.next !null) { if(curr.next.val val){ curr.next curr.next.next; } else { curr curr.next; } } return head; }注意有的时候会要求我们手撕链表并没有提供ListNode类这时就需要我们自己写代码如下public class ListNode { // 结点的值 int val; // 下一个结点 ListNode next; // 节点的构造函数(无参) public ListNode() { } // 节点的构造函数(有一个参数) public ListNode(int val) { this.val val; } // 节点的构造函数(有两个参数) public ListNode(int val, ListNode next) { this.val val; this.next next; } }题目解析由于LeetCode里给我们定义好了ListCode类我们在这里直接使用一开始我们写一个while循环先判断第一个节点是不是空指针同时是否是我们要删除的目标值为什么第一个头节点我们要单独的列出来因为在链表中如果要删除一个节点通常都要知道这个节点的前驱节点除了头节点因为没有前驱节点所以我们要先处理这个特殊情况如果第一个就是要删除的目标值那我们直接把下一个节点的值给这个头节点相当于覆盖的操作关于这里为什么用while而不是if有的同学认为只是判断一次if和while都一样恰恰相反这里的while就是为了处理多次如果链表的元素都相同那么删除完第一个头节点接下来还要删除所以不一定只是一次删除用了一次只能删除一次。然后下面就是处理一般的节点我们先定义一个指针因为链表不是连续的并不是像数组那样可以通过操作索引因此我们需要定义一个指针来记录位置通过指针来导航同时用while循环指针也需要做非空判断指针的下一个节点也不能是空接下来我们就判断指针下个节点的值是不是目标值如果是目标值我们把指针下下个的节点赋值给被删除的节点覆盖操作如果不等于目标值那么就移动指针的位置继续判断下面的节点。完整执行示例链表1 → 2 → 2 → 3 → 4删除 val2java初始currhead1 第1轮循环 curr1, curr.next2 检查2 2? true → 删除 执行curr.next curr.next.next (1.next 2的next) 链表变成1 → 2 → 3 → 4 curr保持1不移动 第2轮循环 curr1, curr.next2新的下一个 检查2 2? true → 删除 执行curr.next curr.next.next (1.next 2的next) 链表变成1 → 3 → 4 curr保持1不移动 第3轮循环 curr1, curr.next3 检查3 2? false → 执行else curr curr.next (curr3) 链表不变1 → 3 → 4 第4轮循环 curr3, curr.next4 检查4 2? false → 执行else curr curr.next (curr4) 第5轮循环 curr4, curr.nextnull 检查条件curr.next ! null? false → 循环结束 最终结果1 → 3 → 4 ✅可视化理解text链表1 → 2 → 3 → 4删除 2 删除过程 1 → 2 → 3 → 4 ↑ curr 发现 curr.next2 需要删除 1 → 3 → 4 ← 删除2curr不动 ↑ curr 发现 curr.next3 不需要删除 1 → 3 → 4 ↑ curr (移动了) 发现 curr.next4 不需要删除 1 → 3 → 4 ↑ curr (移动了) curr.nextnull结束核心要点while 条件确保安全既要当前节点存在也要下一个节点存在删除时不移动 curr因为删除后新的 curr.next 需要重新检查不删除时移动 curr当前节点安全可以继续检查下一个这个技巧避免了使用前驱指针通过永远检查下一个节点来简化逻辑这就是为什么这个方法只用了一个指针curr就能完成删除操作第二种解法双指针/** * 方法1 * 时间复杂度 O(n) * 空间复杂度 O(1) * param head * param val * return */ public ListNode removeElements(ListNode head, int val) { while (head ! null head.val val) { head head.next; } // 已经为null提前退出 if (head null) { return head; } // 已确定当前head.val ! val ListNode pre head; ListNode cur head.next; while (cur ! null) { if (cur.val val) { pre.next cur.next; } else { pre cur; } cur cur.next; } return head; }题目解析这种解法就是通过双指针的操作更直观的理解代码其中这里有个提前退出的代码为什么方法一没有呢这个代码是为了防止删除头节点之后变成了空链表因为方法一已经在下面的while循环中加了限制条件。判断非空之后定义两个指针先判断头节点之后的因为头节点事先判断过了如果等于那么就把这个节点的下一个节点赋值给被删除的也就是pre.nextcur 是引用它只是指向节点不是节点本身修改 cur只改变引用指向不影响链表结构修改 pre.next改变链表的连接关系真正删除节点删除必须改前驱链表删除的本质是让前驱节点的 next 指向被删节点的 next记忆口诀要删除节点必须动它的爸爸的 next 指针方法三虚拟头节点/** * 时间复杂度 O(n) * 空间复杂度 O(1) * param head * param val * return */ public ListNode removeElements(ListNode head, int val) { // 设置一个虚拟的头结点 ListNode dummy new ListNode(); dummy.next head; ListNode cur dummy; while (cur.next ! null) { if (cur.next.val val) { cur.next cur.next.next; } else { cur cur.next; } } return dummy.next; }题目分析既然我们在上面的方法中每次都要处理第一个头节点总感觉有点麻烦那么有没有不需要处理的方法呢当然有那就是我么自己设置一个虚拟头节点那这个虚拟节点之后的节点都是常规的节点能用通用的解法也就是平级的了。设置一个指针初始位置就是虚拟头节点然后下面就是常规的判断最后return的时候返回的是我们真正的头节点也就是dummy.next。虚拟头节点是我们自己创建的默认非空。结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励