AcWing刷题笔记-29-删除链表中重复的节点

题目信息

平台：AcWing
题目链接：删除链表中重复的节点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5

初步思路

链表删除的经典题，核心难点在于重复节点一个不留。由于链表的头节点本身也可能被删除（比如 [1,1,1]），所以需要使用虚拟头节点 dummy 来统一处理边界。

这里总结两种写法，核心思想一致，都是双指针遍历，区别在于代码组织方式。

算法分析

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

代码实现（C++）

写法 1：指针指向下一个节点，再整体删除重复段

class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy->next = head;

        auto cur = dummy;
        while (cur->next && cur->next->next) {
            int val = cur->next->val;
            if (cur->next->next->val == val) {
                while (cur->next && cur->next->val == val)
                    cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

写法 2：指针在移动的时候就开始删除重复段

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy->next = 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 && val == cur->next->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`	`NULL`	所有节点都重复，返回空链表

总结与反思

这道题和 LeetCode 82 题本质上是同一道题，核心在于如何处理「删除一段连续重复节点」的场景。

两种写法的区别很细微：

写法 1 先取出 val = cur->next->val，然后用 cur->next->next->val == val 判断是否重复。这种写法更直观，但需要注意 cur->next->next 的判空。
写法 2 直接用 cur->next->val == cur->next->next->val 判断，更符合「先看相邻两个是否相等」的直觉。

实际调试时容易踩的坑：

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

TK的小站