LeetCode 203. 移除链表元素

约 4 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 2-5 阿里 美团 快手 滴滴
标签
链表 递归

题目描述

✅ 203. 移除链表元素

image-20260928224000314

image-20260928224000315

题意分析

删除单链表中所有值等于 val 的节点，保留其他节点的原顺序，返回修改后的头节点。目标可能连续出现，也可能位于开头或末尾，链表甚至会被全部删除。

删除不是让一个局部指针向后移动，而是修改前驱节点的 next，让它跳过目标节点。为了让头节点也拥有可操作的前驱，可以在原头之前增加一个虚拟节点。

解法：虚拟头节点迭代删除

核心思路

[!blue]

创建 dummy 指向原头，令 cur 从 dummy 开始。cur 始终是已确认保留部分的最后一个节点，或最初的虚拟头；真正待检查的是它的后继 cur.next。

如果后继值等于目标，执行 cur.next = cur.next.next，直接跳过它。此时 cur 不移动，因为刚接上来的新后继还没有检查，它也可能需要删除。这样可以连续删除任意长度的目标片段，而不会漏过相邻节点。

如果后继值不等于目标，就确定它应保留，令 cur = cur.next，把已确认部分向后扩展一个节点。每一轮都会处理掉一个待检查的真实节点，剩余节点的顺序没有变化，最终在后继为空时结束。

虚拟头只提供一个稳定的入口，不参与值比较。头部被删除时更新的是 dummy.next，全部删空时它变为空；因此结果应从 dummy.next 取得，而不是返回可能已经被删除的原头。

解题步骤

  1. 创建虚拟头 dummy，指向 head，令 cur = dummy。
  2. 只要 cur.next 非空，就检查其节点值。
  3. 等于 val 时跳过后继，并保持 cur 不动。
  4. 否则移动到该保留节点，继续检查它的后继。
  5. 没有后继后返回 dummy.next；原链表为空时也自然返回空。

代码实现

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);

        dummy.next = head;
        ListNode cur = dummy;

        while (cur.next != null) {
            if (cur.next.val == val) {
                // 删除后前驱不动，继续检查新接上的后继，避免漏删连续目标
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }

        return dummy.next;
    }
}

func removeElements(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head}
    cur := dummy
    for cur.Next != nil {
        if cur.Next.Val == val {
            // 删除后前驱不动，继续检查新接上的后继，避免漏删连续目标
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return dummy.Next
}

复杂度分析

  • 时间复杂度：$O(n)$，每个真实节点作为后继检查一次。
  • 空间复杂度：$O(1)$，虚拟头与游标。

关键点总结

[!green]

  • 删的是后继链接，不是单纯移动局部变量。
  • 已确认保留区间不包括虚拟节点的占位值。

易错点总结

[!yellow]

  • 删除后仍前进，会跳过新接来的待删节点。
  • 从真实头开始检查后继，会漏掉头本身。
  • 返回原头可能把已删除头部重新交回。

相似题目

题目 难度 关联与区别
27. 移除元素 简单 同样删除指定值，数组用覆盖压缩，链表通过前驱next跳过节点。
82. 删除排序链表中的重复元素 II 中等 同样用哑节点处理可能被删的头段，原题先判断重复值段，本题按固定值筛选。
19. 删除链表的倒数第 N 个结点 中等 用哨兵与前驱节点统一链表删改边界；本题过滤所有目标值节点，该题先用指针间隔定位倒数节点。
83. 删除排序链表中的重复元素 简单 用哨兵与前驱节点统一链表删改边界；本题过滤所有目标值节点，该题每段重复值只保留一个。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/17566770
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！