1 题目描述
203. 移除链表元素要求给定一个链表的头节点 head
和一个整数 val
,任务是删除链表中所有满足 Node.val == val
的节点,并返回新的头节点。
2 解题思路
- 使用虚拟头节点:为了简化边界情况(例如当头节点需要被删除时),我们可以创建一个虚拟头节点
dummy
,它指向原链表的头节点。这样可以避免额外的条件判断。 - 遍历链表:通过一个指针
cur
遍历链表,每次检查cur.next
节点是否需要被删除。 - 删除节点:如果
cur.next
的值等于val
,则将cur.next
指向下一个节点(即跳过当前节点);否则,将cur
向前移动一位。 - 返回结果:最后返回
dummy.next
即为新的链表头节点。
3 Java 代码实现
public class Solution {
public ListNode removeElements(ListNode head, int val) {
// 创建虚拟头节点
ListNode dummy = new ListNode(-1, head);
// 初始化 cur 指针指向虚拟头节点
ListNode cur = dummy;
// 遍历链表
while (cur.next != null) {
// 如果找到值为 val 的节点,则删除该节点
if (cur.next.val == val) {
cur.next = cur.next.next;
} else {
// 否则,继续向前移动
cur = cur.next;
}
}
// 返回新链表的头节点
return dummy.next;
}
}```
- **时间复杂度:** O(n),其中 n 是链表中的节点数量。我们需要遍历整个链表一次。
- **空间复杂度:** O(1),只需要常量级额外空间。
# 4 注意事项
- **哑节点**:引入哑节点 `dummy` 以简化代码逻辑,避免处理头节点的特殊情况。
- **遍历链表**:使用 `cur` 指针来遍历链表,处理每一个节点。
- **删除节点**:当遇到值为 `val` 的节点时,直接跳过该节点,不改变 `cur` 指针的位置。
- **返回新头节点**:返回 `dummy.next` 作为新的链表头节点。