0203.移除链表元素

难度：🟢 简单

标签：链表、递归

链接：203. 移除链表元素

题目描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == 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
输出：[]

解题思路

核心思想

本题的目标是在原地移除一个链表中所有值等于 val 的节点。核心挑战在于，当需要删除的节点是头节点时，处理逻辑会与删除中间节点或尾节点不同。为了统一所有情况，简化代码逻辑，我们可以引入一个“虚拟头节点”。

思路选择

迭代法 + 虚拟头节点（Dummy Head） 是解决此问题的标准最优思路。

• 虚拟头节点：我们创建一个 dummyHead 节点，让它的 next 指向原始的 head。这样一来，原始链表中的所有节点（包括头节点）都变成了“中间节点”，都有一个前驱节点。这使得删除操作的逻辑完全统一。

• 单指针遍历：我们使用一个指针 current，它始终指向我们正在检查的节点的 前一个节点。current 从 dummyHead 开始。我们通过 current.next 来访问和判断当前节点。

关键步骤

1. 创建虚拟头节点：const dummyHead = new ListNode(0, head)。

2. 初始化指针：创建一个指针 current = dummyHead。

3. 循环遍历：当 current.next 不为空时，持续循环（即只要还有节点需要检查）。

4. 判断与删除： a. 如果 current.next 的值等于 val，说明找到了要删除的节点。我们通过 current.next = current.next.next 来跳过（即删除）这个节点。注意，此时 current 指针 不移动，因为它需要继续检查新的 current.next（以处理连续多个待删除节点的情况）。 b. 如果 current.next 的值不等于 val，说明这个节点需要保留。我们将 current 指针后移一位 current = current.next。

5. 返回结果：循环结束后，返回 dummyHead.next，它指向的是处理后新链表的头节点。

代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 * this.val = (val===undefined ? 0 : val)
 * this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const dummyHead = new ListNode(0, head);
    let current = dummyHead;

    while (current.next !== null) {
        if (current.next.val === val) {
            // 删除 current 后面的节点
            current.next = current.next.next;
        } else {
            // 保留 current 后面的节点，移动 current
            current = current.next;
        }
    }

    return dummyHead.next;
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是链表的长度。我们只需要对链表进行一次完整的遍历。

• 空间复杂度：O(1) 我们只使用了 dummyHead 和 current 等常数个额外变量，空间消耗是恒定的。

相关题目

• 0027.移除元素

• 0083.删除排序链表中的重复元素

• 0206.反转链表

总结

本题是链表删除操作的基础题目，其核心在于虚拟头节点（Dummy Head）技巧的运用。通过引入一个伪头节点，可以避免为“删除真正的头节点”编写额外的 if-else 判断，使得代码更加简洁、通用和健壮。这是处理链表修改类问题时必须掌握的重要技巧。