LeetCode【刷题日记】一篇搞懂链表的删除
🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：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.val==val) { 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，删除 val=2
java
初始：curr=head=1 第1轮循环： curr=1, curr.next=2 检查：2 == 2? true → 删除 执行：curr.next = curr.next.next (1.next = 2的next) 链表变成：1 → 2 → 3 → 4 curr保持=1（不移动） 第2轮循环： curr=1, curr.next=2（新的下一个） 检查：2 == 2? true → 删除 执行：curr.next = curr.next.next (1.next = 2的next) 链表变成：1 → 3 → 4 curr保持=1（不移动） 第3轮循环： curr=1, curr.next=3 检查：3 == 2? false → 执行else curr = curr.next (curr=3) 链表不变：1 → 3 → 4 第4轮循环： curr=3, curr.next=4 检查：4 == 2? false → 执行else curr = curr.next (curr=4) 第5轮循环： curr=4, curr.next=null 检查条件：curr.next != null? false → 循环结束 最终结果：1 → 3 → 4 ✅
可视化理解
text
链表：1 → 2 → 3 → 4，删除 2 删除过程： 1 → 2 → 3 → 4 ↑ curr 发现 curr.next=2 需要删除： 1 → 3 → 4 ← 删除2，curr不动 ↑ curr 发现 curr.next=3 不需要删除： 1 → 3 → 4 ↑ curr (移动了) 发现 curr.next=4 不需要删除： 1 → 3 → 4 ↑ curr (移动了) curr.next=null，结束
核心要点
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.next
cur 是引用：它只是"指向"节点，不是节点本身
修改 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。虚拟头节点是我们自己创建的，默认非空。
结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！