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

2026-08-06 HGNULB 约 4 分钟

文章信息 23 个分类 4 个标签

分类

LeetCode CodeTop 中等已解决需加强 100-200 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度滴滴拼多多网易小米商汤旷视亚马逊虾皮面试经典 150 题

题目描述

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

题意分析

输入一条按值升序排列的链表，要求删除所有「出现过重复」的节点，只留下在原链表中恰好出现一次的值，返回处理后的链表头。

这里最容易读错的是「删除重复元素」的口径。本题不是「每种值保留一个」，而是整段丢弃：[1,1,2] 的答案是 [2]，两个 1 都要没，不能留一个。这一点是它与 83 题唯一但决定性的差别。

「已排序」这个前提提供了关键信号：相同的值必然连续出现。于是「某个值是否重复」这个原本需要全局统计的问题，退化成只看当前节点和它的下一个节点是否相等——不需要任何额外的全局记录，也不需要第二遍扫描。

另一个必须提前意识到的点是，被删除的节点可以是头节点（[1,1,2] 就是），所以返回值不一定是传进来的 head，任何直接返回 head 的写法都错。

需要单独想清楚的边界：空链表；只有一个节点；所有节点同值（[1,1] 应返回空链表）；重复段落在末尾（[1,2,2] 应返回 [1]）；连续出现多个重复段（[1,1,2,2] 应返回空链表）；重复段长度大于 2（[1,1,1,2] 的三个 1 要一次删净）。

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

核心思路

链表已排序，相同值必然连续。用哨兵节点统一处理头部删除，pre 始终指向已确认保留部分的末尾；发现重复值后，保持 pre 不动并跳过整段。

解题步骤

在头节点前添加哨兵节点，初始化 pre = dummy。

若 pre.next 与后继值不同，当前节点只出现一次，pre 向前移动。

若值相同，记录该值并不断修改 pre.next，直到越过整段。

返回 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)$，每个节点最多被访问一次。

空间复杂度：$O(1)$。

关键点总结

本题要删除重复值的所有节点，不是每个值保留一个。

哨兵节点让头部重复段与中间重复段使用同一套删除逻辑。

删除重复段时 pre 不能移动，新接上的节点仍需检查。

易错点总结

只删除重复段中的部分节点，会错误地留下一个重复值。

内层循环必须先判空，重复段可能一直延伸到链表末尾。

应返回 dummy.next，因为原头节点可能已被删除。

相似题目

题目	难度	考察点
83. 删除排序链表中的重复元素	简单	每段保留一个而不是整段删除，因此头节点绝不会被删，连哨兵都可以省
203. 移除链表元素	简单	删除条件由「与邻居相等」变成「等于给定值」，不再需要有序，是哨兵模板的最简形
237. 删除链表中的节点	中等	拿不到前驱节点，只能把后继的值复制过来再删后继，考的是「删除等价于覆盖」
剑指 Offer 18. 删除链表的节点	简单	按值删除且只删一个，找到即可返回，不需要处理连续段
面试题 02.01. 移除重复节点	简单	链表无序，同值不再相邻，必须靠哈希集合记录出现过的值
面试题 02.03. 删除中间节点	简单	只给待删节点本身，同样用「复制后继再摘后继」的技巧，与去重逻辑无关