CodeBrick 博客

Appearance

删除排序链表的重复元素：一趟相邻比较 ​

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。这道题和 2015·41 链表按绝对值去重看着像同一类题，其实性质完全不同——2015·41 的链表是任意顺序，靠值域标记数组换时间；本题的链表已排序，重复值必然相邻，靠有序性一趟解决，用不上标记数组。它是经典训练题，不是真题，也不押题。

题目 ​

给定一个按值升序排列的单链表 head，删除所有重复出现的结点，使得每个值只保留一个，返回处理后的链表头。例如 1 → 1 → 2 → 3 → 3 → 3 → 4 处理后为 1 → 2 → 3 → 4。链表结点定义如下：

c
typedef struct node {
    int val;
    struct node *next;
} NODE;

这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——直白写法就是最优解，力气花在把边界写准上。

直观解法：一趟相邻比较 ​

已排序是这道题最重要的前提：值相同的结点在链表里必然挨在一起，不会被其他值隔开。这意味着判断「当前结点是不是重复」，只需要看它和紧挨着的下一个结点是否同值，完全不需要跟前面所有出现过的值比对。

c
NODE *deleteDuplicates(NODE *head) {
    NODE *cur = head;
    while (cur != NULL && cur->next != NULL) {
        if (cur->val == cur->next->val) {
            NODE *dup = cur->next;
            cur->next = cur->next->next;   // 跳过重复结点
            free(dup);
            // cur 不前进，继续跟新的 cur->next 比较，处理连续三个及以上重复的情况
        } else {
            cur = cur->next;               // 值不同才前进
        }
    }
    return head;
}

拿 1 → 1 → 2 → 3 → 3 → 3 → 4 走一遍：cur 指向第一个 1，cur->next 也是 1，删掉后一个 1，cur 不动；此时 cur->next 变成 2，值不同，cur 前进到 2；cur->next 是 3，值不同，cur 前进到第一个 3；cur->next 是第二个 3，删掉，cur 不动；cur->next 变成第三个 3，仍相同，再删一次，cur 不动；此时 cur->next 变成 4，值不同，cur 前进到 4；cur->next 为 NULL，循环结束。结果 1 → 2 → 3 → 4 ✓——连续三个重复值被正确压缩成一个。

复杂度：cur 最多把整条链表走一遍（每次不是删除就是前进，两种操作合计不超过 n 次），时间 O(n)；只用了 cur、dup 两个指针，空间 O(1)。

为什么它就是满分解 ​

用总纲的「找浪费三问」审一遍，三问全部答「没有」：

  1. 有没有重复扫描？ 没有。每个结点只在 cur 或 cur->next 的位置被检查一次，删除操作直接摘链，不需要回头重新扫描前面已经处理过的部分。
  2. 有没有重算已知的东西？ 没有。判断「当前值是否重复」只看相邻的下一个结点，不需要维护任何「之前出现过哪些值」的额外记录。
  3. 有没有放着性质不用？ 没有。题目给的「已排序」性质，正好被「重复值必然相邻」这个推论直接利用，一趟相邻比较就够了。

更根本的一条：删除链表里的重复元素，至少要把每个结点看一遍才能确认它是否重复——读一遍链表就是 O(n) 的下界，任何正确算法都躲不开。碰到下界，就没有优化空间，直观写法即最优。

和 2015·41 的区别，别混着用 ​

这道题最容易和真题 2015·41搞混，两者表面都是「链表去重」，但依赖的性质完全不同：

  • 本题：链表已经升序排列，重复值必然相邻，一趟相邻比较（cur 和 cur->next）就能删干净，不需要任何辅助空间。
  • 2015·41：链表是任意顺序（结点顺序不保证有序），要删的是「绝对值相等」的结点，且相等的两个结点在链表里可能隔得很远。这种情况下相邻比较毫无意义，必须借助值域标记数组（利用 |data| ≤ n 这个值域约束）记住「这个绝对值是否已经出现过」，这才是空间换时间的用武之地。

一句话区分：相邻比较靠「有序性」，标记数组靠「值域约束」，用错了性质，本题套标记数组是杀鸡用牛刀（多开 O(n) 空间却没有必要），2015·41 套相邻比较则直接错——它的链表根本不保证有序。

真正的难点在这里 ​

分不在优化上，在把这两处边界写准：

  • 删除后 cur 不能前进。这是全题最容易写错的一步：删掉 cur->next 之后，新的 cur->next 可能和 cur 仍然相同（连续三个及以上重复值），必须让 cur 停在原地、继续比较新的 cur->next，直到不再相同才前进。如果每次判断后都无条件前进，连续重复值只会删掉一部分。
  • 循环条件 cur != NULL && cur->next != NULL：既要防止空链表时访问 cur->val 越界，也要防止 cur 走到最后一个结点时访问 cur->next->val 越界。

一趟比较,看一遍 ​

用 1 → 1 → 2 → 3 → 3 → 3 → 4 演示——连续三个 3 被逐个摘除、压缩成一个：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足 ​

这道题结构简单,过度设计的空间不大,但有一个常见的「想复杂了」：

  • 想套用 2015·41 的值域标记数组。已排序链表根本用不上「记住出现过哪些值」这一套——相邻比较已经是 O(n) 时间 O(1) 空间，标记数组不但多开销空间，还得先假设一个值域范围，纯属多此一举。

下一步 ​

相关真题（1题）

2017Q11选择题2分
去刷题

链式存储排序：链式存储对各排序算法效率的影响

单链表