题目

力扣题目

给定单链表的头节点 head 和整数 val，删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

示例 1：

Text
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

Text
输入：head = [], val = 1
输出：[]

示例 3：

Text
输入：head = [7,7,7,7], val = 7
输出：[]

提示：

  • 链表节点数在 [0, 10^4] 范围内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

考察内容

  • 单链表节点的删除与重新连接
  • 头节点变化的特殊性
  • 使用虚拟头节点统一删除逻辑
  • 删除节点后的指针移动
  • 动态内存释放

解题思路

直接操作原链表

普通节点有前驱节点，可以通过 previous->next = deleted->next 将它移出链表。但头节点没有前驱，因此需要先单独删除所有值等于 val 的连续头节点，再处理剩余节点。

如果头部节点全部被删除，head 会变成 nullptr，后续遍历必须正确处理这一情况。

虚拟头节点

更推荐在原头节点前创建一个虚拟节点 dummy：

Text
dummy → head → ...

这样原头节点也变成了一个“有前驱的普通节点”。令 cur 指向 dummy，每轮检查 cur->next：

  • 若 cur->next->val == val，删除 cur->next，但 cur 保持不动；
  • 否则将 cur 移动到下一个节点。

删除节点时不能立即移动 cur，因为新接到 cur->next 的节点可能仍然等于 val。例如 [7,7,7] 必须在同一个前驱位置连续删除。

以 [1,2,6,3,4,5,6]、val = 6 为例：

  1. dummy 指向原头节点 1；
  2. cur 依次经过 1、2；
  3. 发现 cur->next 是 6，令 cur->next 跳到 3 并释放旧节点；
  4. 继续遍历，在尾部用相同逻辑删除第二个 6；
  5. 返回 dummy.next，即新的真实头节点。

⤢ 打开

  • 时间复杂度：O(n)O(n)，每个节点最多检查一次
  • 空间复杂度：O(1)O(1)

代码演示

C++
struct ListNode {
    int val;
    ListNode* next;

    ListNode() : val(0), next(nullptr) {}
    explicit ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

// 推荐写法：虚拟头节点统一处理所有位置
ListNode* removeElements(ListNode* head, int val) {
    ListNode dummy(0, head);
    ListNode* cur = &dummy;

    while (cur->next != nullptr) {
        if (cur->next->val == val) {
            ListNode* deleted = cur->next;
            cur->next = deleted->next;
            delete deleted;
        } else {
            cur = cur->next;
        }
    }

    return dummy.next;
}

// 不使用虚拟头节点：需要单独处理链表头部
ListNode* removeElementsWithoutDummy(ListNode* head, int val) {
    while (head != nullptr && head->val == val) {
        ListNode* deleted = head;
        head = head->next;
        delete deleted;
    }

    ListNode* cur = head;
    while (cur != nullptr && cur->next != nullptr) {
        if (cur->next->val == val) {
            ListNode* deleted = cur->next;
            cur->next = deleted->next;
            delete deleted;
        } else {
            cur = cur->next;
        }
    }

    return head;
}

易错点

  • 忽略头节点可能被删除：删除原头节点后，函数需要返回新的 head。
  • 删除后仍移动 cur：新接入的下一个节点可能也需要删除，应保持 cur 不动并继续检查。
  • 先释放节点再读取 next：delete 后不能再访问该节点；应先完成链表连接，再释放节点。
  • 删除所有头节点后解引用空指针：直接写法的遍历条件必须包含 cur != nullptr。
  • 返回虚拟节点地址：dummy 是局部变量，应该返回 dummy.next，不能返回 &dummy。
  • 忘记释放被移除的节点：在手动管理内存的 C++ 环境中，应对断开的节点执行 delete。

总结

虚拟头节点为原链表增加了一个稳定的前驱，使头节点与中间节点可以使用完全相同的删除逻辑。链表题中只要头节点可能变化，优先考虑 dummy 通常能显著减少分支和边界错误。

相关题目

    1. 删除链表的倒数第 N 个结点
    1. 合并两个有序链表
    1. 删除排序链表中的重复元素
    1. 反转链表
    1. 设计链表