1 题目描述

203. 移除链表元素要求给定一个链表的头节点 head 和一个整数 val，任务是删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

2 解题思路

1. 使用虚拟头节点：为了简化边界情况（例如当头节点需要被删除时），我们可以创建一个虚拟头节点 dummy，它指向原链表的头节点。这样可以避免额外的条件判断。
2. 遍历链表：通过一个指针 cur 遍历链表，每次检查 cur.next 节点是否需要被删除。
3. 删除节点：如果 cur.next 的值等于 val，则将 cur.next 指向下一个节点（即跳过当前节点）；否则，将 cur 向前移动一位。
4. 返回结果：最后返回 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` 作为新的链表头节点。