LeetCode 82. 删除排序链表中的重复元素 II

约 5 分钟
文章信息 25 个分类 2 个标签
分类
LeetCode CodeTop 中等 已解决 需加强 100-200 面试经典 150 题 腾讯 字节 阿里 微软 亚马逊 美团 拼多多 京东 小米 百度 网易 快手 滴滴 虾皮 招行 商汤 旷视 猿辅导
标签
双指针 链表

题目描述

✅ 82. 删除排序链表中的重复元素 II

image-20260928191420094

image-20260928191420095

题意分析

给定一个按非递减顺序排列的链表，删除所有出现次数超过一次的值所对应的节点，只保留在原链表中恰好出现一次的值。某个值一旦重复，它的所有节点都要删除，不能留下其中一个。

返回处理后的头节点，保留节点的顺序不变。输入可能为空，重复段也可能位于头部、尾部或连续出现；若每个值都重复，结果就是空链表。链表已经有序，所以相同值一定连在一起，可以按连续的一段来判断是否保留。

解法：哨兵节点跳过重复段

核心思路

[!blue]

在头节点前添加哨兵 dummy，用 pre 指向已经确认保留部分的最后一个节点。初始还没有保留任何节点，令 pre = dummy；每轮需要判断的第一个节点是 pre.next。

若 pre.next 与它的后继值不同，当前值在这一段中只出现一次。由于链表有序，相同值不可能隔开出现；此前的段也已经完整处理，所以这个节点可以保留，让 pre 前进一步。

若两者值相同，说明遇到了重复段。先保存重复值 duplicate，再不断执行 pre.next = pre.next.next，直到 pre.next 为空或值不再等于 duplicate。这样会删掉这一段的所有节点，包括最开始发现的那个节点。

删除期间以及删除之后，pre 都不前进：它仍是已保留部分的末尾，而新接上的 pre.next 尚未判断，也可能属于另一段重复值。只有确定某个节点应当保留，才能推进 pre。

当未处理部分只剩零个或一个节点时，已无法形成新的重复段；之前遇到的重复值又都已整段删除，因此剩下的单个节点可以直接保留。最终从 dummy.next 取得结果，头部是否被删除不需要额外分支。

解题步骤

  1. 创建指向 head 的哨兵，令 pre = dummy。
  2. 当 pre.next 和 pre.next.next 都存在时，比较它们的值。
  3. 若不同，保留 pre.next，执行 pre = pre.next。
  4. 若相同，记录重复值；只要 pre.next 存在且值等于它，就把该节点从连接中跳过。删除整段后保持 pre 不变，继续检查新接上的节点。
  5. 未处理部分不足两个节点时结束，返回 dummy.next。

代码实现

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;

        while (pre.next != null && pre.next.next != null) {
            if (pre.next.val != pre.next.next.val) {
                pre = pre.next;
            } else {
                // 记下重复值，整段都删除，前驱暂时不移动。
                int duplicate = pre.next.val;

                // 重复段可能延伸到末尾，每次读取前先检查节点存在。
                while (pre.next != null && pre.next.val == duplicate) {
                    pre.next = pre.next.next;
                }
            }
        }

        return dummy.next;
    }
}

func deleteDuplicates(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    pre := dummy

    for pre.Next != nil && pre.Next.Next != nil {
        if pre.Next.Val != pre.Next.Next.Val {
            pre = pre.Next
        } else {
            // 记下重复值，整段都删除，前驱暂时不移动。
            duplicate := pre.Next.Val
            // 重复段可能延伸到末尾，每次读取前先检查节点存在。
            for pre.Next != nil && pre.Next.Val == duplicate {
                pre.Next = pre.Next.Next
            }
        }
    }
    return dummy.Next
}

复杂度分析

  • 时间复杂度：$O(n)$，n 为节点数。每个节点要么被 pre 越过并保留，要么被跳过并删除；内层循环只消耗当前重复段，不会重新扫描已经处理的节点。
  • 空间复杂度：$O(1)$，只使用哨兵、前驱指针和重复值变量。

关键点总结

[!green]

  • 利用有序性，把相同值视为一个连续段：长度为一就保留，长度大于一就整段删除。
  • pre 始终指向已确认保留部分的末尾，pre.next 才是下一轮的待判节点。
  • 保留一个节点时推进 pre，删除一段时只修改 pre.next。

易错点总结

[!yellow]

  • 只删掉后面的重复节点会留下一个重复值，不符合本题“只保留原来出现一次的值”的要求。
  • 删除整段后直接推进 pre，会跳过新接上的节点，导致连续的重复段处理不全。
  • 必须先保存重复值，再修改连接；否则判断基准可能随 pre.next 改变，把后面的其他值一起删除。
  • 读取节点值之前先判空，因为重复段可能一直延伸到末尾。
  • 原头节点可能被删除，返回值必须是 dummy.next。

相似题目

题目 难度 关联与区别
83. 删除排序链表中的重复元素 简单 原题把每段重复值保留一个，本题只要某值重复就整段删除，前驱推进规则不同。
203. 移除链表元素 简单 同样用哑节点与前驱删除一段节点，原题按指定值删除，本题先识别重复段。
19. 删除链表的倒数第 N 个结点 中等 用哨兵与前驱节点统一链表删改边界；本题删除整段重复值，该题先用指针间隔定位倒数节点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/62704507
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！