面试题18（二）：删除链表中重复的节点

从“去重到底保留几个”开始

先预测：输入排序链表 1→2→3→3→4→4→5，输出应该是 1→2→3→4→5，还是 1→2→5？

题目“删除链表中重复的节点”的契约是第二种：只要某个值出现超过一次，该值对应的节点就要**全部删除**。它不是常见的“相邻重复只保留一个”，也不是只删除多出来的副本。两个 3 和两个 4 都不再出现在结果中，因此作者示例输出为 1→2→5。

提供了关键结构：相同值一定聚在一个连续区间。把这个区间称为。扫描到当前节点时，只比较它和后继的值，就能判断当前值是否开始重复；一旦重复，再向后越过所有相同值即可找到下一段不同值。

如果输入未排序，例如 1→2→1，两个 1 不相邻，局部比较不会发现它们属于同一重复值。要支持无序链表，必须先排序、使用哈希计数后第二次扫描，或用额外结构记录出现次数；本题的一次扫描结论严格依赖“排序链表”前置条件。

前驱只指向已经确定保留的节点

维护两个位置：

1. current 指向尚未处理的第一节点。
2. pre 指向已经确定保留的最后一节点；若还没有保留节点，pre 为空。

若 current 与 next 的值不同，current 只出现一次，可以保留它：令 pre=current，current=next。若二者值相同，就记录该值并删除连续的整段；删除后 current 指向首个不同值。此时 pre 不动，因为被删段中没有任何节点可以成为保留前驱。

这就是不变量：pre 后面的链接始终通向“尚未处理的第一节点”。删除中间重复段后，要做的链接更新正是 pre->next = current，其中 current 已经是下一段不同值。

因此“前驱节点与下一段不同值”构成一次删除后的两端：左端是最后一个保留节点，右端是尚未判断但值已不同的节点。中间所有同值节点已经释放。只要每轮恢复这条连接，已处理前缀就不会残留重复值，也不会丢失后续链表。

头部重复为何必须改写 head

当重复段从链表头开始时，pre 仍为空，没有 pre->next 可以修改。删除整段后，调用者的 head 必须直接指向 current。若所有节点值都相同，current 最终为空，head 也必须变为空链表。

作者使用 ListNode** pHead 让函数能够更新调用者的头指针。C++ 也可以使用 ListNode*& head。另一种办法是在真实头之前放一个，让头部重复段也拥有前驱；但函数返回时仍要把哨兵的 next 交回给真实 head。

哨兵能减少“pre 为空”的分支，却不能替代释放循环。重复段中的每一个物理节点都拥有独立生命周期，必须逐个保存 next、释放当前节点，再前进；只把前驱链接跨过去会造成整段内存泄漏。

忠实实现整段删除

下面实现沿用作者的裸指针所有权模型。duplicated只表示 current 所在值是否重复；一旦为真，内部循环删除从 current 开始的全部同值节点。

struct ListNode {
    int value;
    ListNode* next = nullptr;
};
 
void deleteDuplicatedNodes(ListNode*& head) {
    ListNode* pre = nullptr;
    ListNode* current = head;
 
    while (current != nullptr) {
        ListNode* next = current->next;
        const bool duplicated =
            next != nullptr && next->value == current->value;
 
        if (!duplicated) {
            pre = current;
            current = next;
            continue;
        }
 
        const int duplicatedValue = current->value;
        while (current != nullptr &&
               current->value == duplicatedValue) {
            ListNode* doomed = current;
            current = current->next;
            delete doomed;
        }
 
        if (pre == nullptr) {
            head = current;
        } else {
            pre->next = current;
        }
    }
}

外层每次要么保留一个节点并前进，要么删除至少两个节点并越过一段。每个节点最多被 current 访问常数次，因此时间复杂度为 O(n)；只使用 pre、current、next 和一个值副本，额外空间为 O(1)。

注意删除循环先保存 current->next，再释放 current。若先 delete 后读取 next，就会解引用生命周期已结束的对象，属于未定义行为。也不能在释放后通过旧 current 读取重复值，所以要在进入循环前复制 duplicatedValue。

用指向链接的指针统一头部与中部

裸指针版本的两个重连分支可以用统一。link 始终指向“拥有 current 的那条指针”：最初是 head 的地址；保留节点后变成其 next 的地址；删除重复段后直接把 *link 改成下一段不同值。

void deleteDuplicatedWithLink(ListNode*& head) {
    ListNode** link = &head;
 
    while (*link != nullptr) {
        ListNode* current = *link;
        if (current->next == nullptr ||
            current->next->value != current->value) {
            link = &current->next;
            continue;
        }
 
        const int value = current->value;
        while (*link != nullptr && (*link)->value == value) {
            ListNode* doomed = *link;
            *link = doomed->next;
            delete doomed;
        }
    }
}

这个版本没有单独的 pre 变量：*link 本身就是未处理后缀的入口。若重复段从头开始，link 仍指向 head；若在中间，link 指向上一个保留节点的 next。它统一了链接操作，但要求读者清楚二级指针的含义，不能把代码变短误认为算法契约改变。

如果链表用 std::unique_ptr 拥有节点，可以让 link 指向拥有当前节点的 unique_ptr，删除动作变为移动后继所有权，释放自动发生：

#include <memory>
 
struct OwnedNode {
    int value;
    std::unique_ptr<OwnedNode> next;
};
 
void deleteDuplicatedOwned(std::unique_ptr<OwnedNode>& head) {
    std::unique_ptr<OwnedNode>* link = &head;
 
    while (*link != nullptr) {
        const int value = (*link)->value;
        auto* probe = (*link)->next.get();
        if (probe == nullptr || probe->value != value) {
            link = &((*link)->next);
            continue;
        }
 
        while (*link != nullptr && (*link)->value == value) {
            *link = std::move((*link)->next);
        }
    }
}

赋值右侧先取得后继所有权，旧节点随后由被覆盖的 unique_ptr 销毁。该写法避免显式 delete 和泄漏，但仍假设链表无环且节点由唯一所有权链管理。若外部还保存裸指针指向被删节点，删除后它们同样悬空。

异常安全和泛型值边界

作者节点值为 int，复制 duplicatedValue 不会抛异常。泛型节点的值复制若可能抛出，异常发生在删除前，链表尚未改变，可以保持原结构；但进入删除循环后不应再执行可能抛出的值操作，否则可能只删掉重复段的一部分。

可以先完成所有潜在失败的比较准备，再提交指针修改。比较运算本身若会抛出，最稳妥的策略是在释放任何节点前先找到整段终点；只有确认边界后再进行无异常的摘链和销毁。析构函数按 C++ 约定也不应抛异常，否则栈展开和所有权容器都无法提供可靠保证。

若值只支持等价比较而不可复制，可以保存对值的引用来扫描边界，但该引用所指节点不能在比较结束前删除。先用 probe 找到首个不同值，再第二次遍历释放整段即可；这仍是线性总时间，因为每个被删节点至多经过查找和释放两次。

外部引用、所有权与接口契约

算法会释放所有重复节点。调用方保存的任何指向这些节点的指针、引用或迭代器都会失效；指向保留节点的引用仍有效。测试不能在删除后读取旧指针来判断值，而应在删除前记录地址数值，之后只检查这些地址不再出现在可达链表中。

共享节点、交叉链表或环形链表都不满足作者模型。若两个头指针共享同一尾段，从其中一条链删除重复节点会让另一条链悬空；若存在环，扫描可能永不结束或重复释放。生产接口应由容器独占节点并隐藏裸链接，或在调试入口验证无环与所有权。

并发遍历时，断链和释放也不是线程安全事务。另一个线程可能刚读取到即将释放的节点。需要互斥锁、读复制更新、危险指针或纪元回收等机制；不能只把 next 改成原子指针就安全地立即 delete。

官方十组测试如何锁定语义

作者测试并非只验证示例。十组输入分别覆盖：部分重复、全部唯一、头部六个相同值、全链同值、所有值都成对、首中尾都有重复、两个不同节点、单节点、两个相同节点以及空链表。

其中几组尤其能区分错误实现：

• 1→1→2 应得到 2，验证头部重连。
• 1→1 应得到空，验证不保留一个副本。
• 1→1→2→2→3→3→4→4 应得到空，验证连续删除多段时 link 或 pre 没有错误前进。
• 1→1→2→3→3→4→5→5 应得到 2→4，验证头、中、尾三处重复段。
• 1→2→3→4→5→6→7 原样保留，验证唯一节点不会被误删。

自动测试除了比较值序列，还应在地址消毒器和泄漏检测下运行。每个测试结束后销毁剩余链表；否则测试夹具泄漏会掩盖算法是否正确释放。空链表和单节点测试也能证明函数不会无条件解引用 head 或 next。

不同去重需求应使用不同函数名

“删除重复节点”在接口层容易歧义。至少有三种常见契约：每个值保留第一个、只删除相邻多余副本、出现多次的值一个不留。本题属于第三种。生产代码应使用 eraseAllRepeatedValues 之类明确命名，并在文档中写出输入必须已排序。

若需求是无序链表中删除所有重复值，可以先用哈希表统计每个值出现次数，再用指向链接的指针删除计数大于一的节点，时间期望 O(n)、空间 O(n)。若不能使用额外空间，可排序后应用本题算法，但排序会改变原节点顺序，且链表排序成本为 O(n log n)。

若输入是数据库游标或流，不能回退且不知道后续是否再次出现相同值，无序情形无法在看到第一个值时立刻决定是否输出。排序前提不仅优化复杂度，也让决策在一个连续重复段结束时即可完成。

正确性证明

循环开始时，head 到 pre 的已处理前缀只包含原链表中出现一次的值，并保持原相对次序；current 是未处理后缀的第一节点。若 current 与后继不同，有序性保证当前值不会在更后面再次出现，所以保留它仍满足不变量。

若 current 与后继相同，有序性保证该值的所有节点都连续位于当前重复段。删除到首个不同值并把 pre 或 head 接到那里，恰好移除了该值的全部节点；其他值的节点没有改变次序。新 current 重新成为未处理后缀入口，不变量恢复。

循环在 current 为空时终止。此时未处理后缀为空，已处理前缀覆盖所有原节点；根据不变量，结果恰好由原链表中只出现一次的值组成。因此算法既不会保留重复值，也不会误删唯一值。

本章练习

概念说明

本章核心概念包括：重复节点全部删除。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 本题输入必须是排序链表，相同值因此形成连续重复段。
2. 重复节点全部删除表示某值出现多次时一个副本也不保留。
3. pre 始终是最后一个保留节点，current 始终是未处理后缀入口。
4. 删除重复段后，把保留前驱或 head 连接到下一段不同值。
5. 每个节点只被常数次访问，时间 O(n)、额外空间 O(1)。
6. 头部重复、全链重复和连续多段删除是最容易写错的边界。
7. 裸指针版本要逐个释放节点，智能指针版本要正确转移所有权。
8. 作者十组测试与内存工具一起验证值序列、链接和生命周期。

名词解释