在Java开发中，自定义链表是灵活度很高的数据结构，当我们需要移除链表中所有等于指定值的元素时，很多新手会直接遍历链表逐个删除，这种方式很容易出现漏删、空指针等问题，效率也不够理想。下面我们就一步步讲解如何实现高效且安全的批量移除操作。
自定义链表的基础结构
首先我们先定义一个简单的单向自定义链表，包含节点类和链表类的基本方法，后续的操作都基于这个结构实现：
// 链表节点类
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
// 自定义链表类
class MyLinkedList {
ListNode head; // 头节点
int size; // 链表长度
// 添加节点到链表尾部
public void add(int val) {
ListNode newNode = new ListNode(val);
if (head == null) {
head = newNode;
} else {
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
}
size++;
}
// 打印链表所有元素
public void printList() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
}常规遍历删除的问题
很多开发者第一反应会写出这样的删除逻辑：遍历链表，遇到值等于目标值的节点就直接删除。但这种方式存在两个明显的问题：
- 如果删除的是头节点，没有提前处理的话，头指针会丢失，后续遍历直接中断
- 删除当前节点后，如果直接移动指针到下一个节点，会跳过当前节点的下一个节点，导致连续出现的指定元素漏删
比如下面这段错误代码，就会出现漏删问题：
// 错误的删除实现示例
public void wrongRemoveAll(int target) {
ListNode cur = head;
while (cur != null) {
if (cur.val == target) {
// 直接删除当前节点，没有处理前驱节点的指向，且会跳过下一个节点
if (cur.next != null) {
cur.val = cur.next.val;
cur.next = cur.next.next;
} else {
// 尾节点删除逻辑缺失，容易空指针
}
}
cur = cur.next;
}
}高效移除的实现方案
方案一：使用虚拟头节点遍历
引入一个虚拟头节点dummy，让它的next指向原链表的头节点，这样所有节点都可以统一处理，不需要单独判断头节点的情况，遍历时用前驱节点来操作删除，避免漏删问题。
// 虚拟头节点方案实现
public void removeAllWithDummy(int target) {
// 创建虚拟头节点，指向原头节点
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy; // 前驱节点，初始指向虚拟头节点
ListNode cur = head; // 当前遍历节点
while (cur != null) {
if (cur.val == target) {
// 当前节点需要删除，前驱节点指向当前节点的下一个节点
prev.next = cur.next;
size--;
} else {
// 当前节点不需要删除，前驱节点移动到当前节点
prev = cur;
}
// 当前节点移动到下一个节点
cur = cur.next;
}
// 更新头节点为虚拟头节点的下一个节点
head = dummy.next;
}方案二：递归实现
如果链表长度不大，也可以采用递归的方式实现，逻辑更简洁，不过递归深度受链表长度限制，长链表可能会有栈溢出的风险。
// 递归方案实现
public void removeAllWithRecursion(int target) {
head = recursionRemove(head, target);
}
private ListNode recursionRemove(ListNode node, int target) {
// 递归终止条件：当前节点为空
if (node == null) {
return null;
}
// 先处理后续节点
node.next = recursionRemove(node.next, target);
// 如果当前节点值等于目标值，返回后续节点，否则返回当前节点
if (node.val == target) {
size--;
return node.next;
} else {
return node;
}
}两种方案的对比
我们可以通过下面的表格对比两种方案的优缺点，根据实际场景选择：
| 方案 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 虚拟头节点遍历 | O(n) | O(1) | 所有场景，尤其是长链表 |
| 递归实现 | O(n) | O(n)（递归栈开销） | 链表长度较短的场景 |
边界场景处理
实际使用中还需要注意几个边界场景，避免程序出现异常：
- 链表为空时，直接返回即可，不需要执行任何操作
- 所有元素都是目标值时，删除后头节点会变为null，虚拟头节点方案已经自动处理了这个问题
- 如果链表存储的是对象而不是基本类型，判断相等需要用
equals方法，而不是==
下面是适配对象类型链表的修改示例，只需要调整判断逻辑即可：
// 存储对象类型的链表节点
class ObjectListNode {
Object val;
ObjectListNode next;
ObjectListNode(Object val) {
this.val = val;
this.next = null;
}
}
// 对象类型链表的移除实现
public void removeAllObject(Object target, ObjectListNode head) {
ObjectListNode dummy = new ObjectListNode(null);
dummy.next = head;
ObjectListNode prev = dummy;
ObjectListNode cur = head;
while (cur != null) {
// 用equals判断对象相等，注意处理null的情况
if ((target == null && cur.val == null) || (target != null && target.equals(cur.val))) {
prev.next = cur.next;
} else {
prev = cur;
}
cur = cur.next;
}
}