LeetCode刷题笔记-82-删除排序链表中的重复元素II

题目信息

平台：LeetCode
题目：82. 删除排序链表中的重复元素 II
难度：Medium
题目链接：删除排序链表中的重复元素 II

题目描述

给定一个已排序的链表的头 head，删除原始链表中所有重复数字的节点，只留下不同的数字。返回已排序的链表。

初步思路

链表删除节点的经典题。由于链表的头节点本身也可能被删除（比如 [1,1,1]），所以第一反应就是使用虚拟头节点 dummy 来统一边界处理。

核心难点在于：重复节点要全部删掉，一个不留。这意味着我们不能简单地「跳过下一个节点」，而是要「跳过一段连续的重复节点」。

算法分析

核心思想：cur 指针遍历链表，每次检查 cur->next 和 cur->next->next 是否值相等。若相等，说明出现重复，记录该值并跳过所有相同值的节点；若不相等，cur 正常后移。
技巧要点：
- 使用 dummy 节点避免对头节点的特殊判断。
- 先判断是否重复，再决定删除，避免误删不重复节点。
- 内层 while 的终止条件要同时判断指针非空和值相等。
时间复杂度：O(n)，每个节点最多被访问两次。
空间复杂度：O(1)，只使用了几个指针。

代码实现（C++）

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        auto dummy = new ListNode(-1, head);
        auto cur = dummy;
        
        while (cur->next && cur->next->next) {
            if (cur->next->val == cur->next->next->val) {
                int val = cur->next->val;
                while (cur->next && cur->next->val == val) {
                    cur->next = cur->next->next;  // 跳过所有重复节点
                }
            } else {
                cur = cur->next;  // 没重复，指针正常后移
            }
        }
        return dummy->next;
    }
};

测试用例

输入	输出	说明
`[1,2,3,3,4,4,5]`	`[1,2,5]`	3 和 4 出现重复，全部删除
`[1,1,1,2,3]`	`[2,3]`	1 出现 3 次，全部删除
`[1,1,1]`	`[]`	所有节点都重复，返回空链表

总结与反思

这道题是链表操作的模板题，核心在于如何处理「删除一段连续重复节点」的场景。我在调试过程中踩了几个坑，值得记录：

必须先判断 cur->next 和 cur->next->next 是否相等，确认真的有重复后，再进入删除逻辑。如果反过来先记录 val 再判断，会导致不重复的节点也被误删。
内层 while 的判空条件必须是 cur->next，而不是 cur->next->next。只判断后者会导致最后一个重复节点漏删，链表会残留一个重复值。
dummy 节点的使用非常重要，它让头节点的删除逻辑和中间节点完全一致，避免了额外的边界处理。

这道题和 83 题（保留一个重复节点）非常像，建议对比记忆。83 题只需要跳过重复节点中的一个即可，而 82 题需要跳过整段重复节点。

TK的小站