企业官网建设流程全解析

“删除链表重复节点”这个题，绝大多数人能在五分钟内写出一个能跑的版本，但如果我再追问一句：链表是无序的怎么办？空间复杂度能不能压到O(1)？如果头节点本身也重复了，你的代码还能正确返回新链表头吗？很多人会卡壳。这篇文章不打算只给一个标准答案，而是把这个题目真正讲透——从问题定义、算法设计、边界条件、内存管理到工程选型，把这条链路上的所有细节都过一遍。无论你是正在学数据结构的学生，还是在准备面试的开发者，亦或是需要在C/C++/Python里手写链表操作的工程师，这篇文章都能给你一套可以直接落地的思路。

1. 先搞清楚“重复节点”到底指什么：三个输入约束决定三种算法

很多人写这道题翻车，不是代码能力不行，而是从一开始就没问清楚需求。链表节点重复，看上去是个非常明确的需求，但落到代码层面，至少有三个完全不同的问题场景。

1.1 链表本身是否有序，直接改变算法路线

如果输入链表是有序的，那问题会简单非常多：重复的节点必然相邻，一次线性扫描就能解决，时间复杂度O(n)，空间复杂度O(1)。如果输入链表是无序的，你就必须先想清楚：是允许用额外空间来记录出现过的值，还是必须在原链表上原地操作。

这两个场景的代码几乎完全不一样。很多人在LeetCode上刷了排序链表的去重题，就开始背代码，结果遇到无序链表去重的变体直接懵住——本质上就是没区分清楚输入约束。

1.2 必须保留一个副本，还是重复的全部删除

“删除重复节点”这句话本身就有歧义。比如链表是1 -> 2 -> 2 -> 3：

• 如果需求是“去重，保留每个值的一个副本”，结果是1 -> 2 -> 3；
• 如果需求是“重复的值一个都不保留”，结果是1 -> 3。

这两个需求在代码上的差距很明显。第二种情况更麻烦，因为头节点可能就是一个重复值，删除后链表的头指针会变化，处理不好就会出现悬空指针或者节点丢失。我见过不少人在第二种需求上栽跟头，明明思路是对的，但头节点的处理写错了，整个链表就断了。

1.3 空间限制：允许哈希表，还是必须O(1)

第三个约束是空间的容忍度。如果允许额外空间，哈希表是最直观的方案，时间O(n)，空间O(n)。如果不允许额外空间，你就得接受O(n log n)的时间复杂度——用归并排序先把链表排好序，再线性去重。

这三组约束排列组合下来，至少有四种不同解法，没有一套代码能通吃所有场景。所以遇到这个题，第一件事不是写代码，而是把约束条件问清楚，这是一种工程思维，不只是刷题技巧。

2. 哈希集合方案：O(n)时间换空间的实现与代价

哈希集合是最快能想到的方案。思路一句话就能说清楚：用一个哈希集合记录已经出现过的值，遍历链表时，如果当前节点的值已经在集合里，就把它从链表中摘除。

2.1 基础实现与指针推进的关键细节

以Python为例，最干净的写法是这样的：

def deleteDuplicatesUnsorted(head: Optional[ListNode]) -> Optional[ListNode]: seen = set() dummy = ListNode(0, head) prev, cur = dummy, head while cur: if cur.val in seen: prev.next = cur.next else: seen.add(cur.val) prev = cur cur = cur.next return dummy.next

注意这里的细节：当发现当前节点是重复节点时，prev.next要跳过去，但prev本身不能动，因为跳过去之后的新prev.next也有可能是重复节点，还需要继续检查。只有当当前节点不重复时，prev才能往前走。这个“删除时prev不动，不删除时prev才移动”的规则，是整个遍历逻辑的核心。

链表操作的另一个核心原则是：先接链，再移动指针。无论你写什么语言，只要涉及到“从链表中摘除节点”，必须保证被摘除节点的后继指针已经在上一轮迭代中被正确保存或引用，否则一旦把指针移走，后面的链表就找不回来了。

2.2 为什么这里用dummy节点而不是直接操作head

头节点本身可能也是重复节点。如果没有dummy节点，当头节点被删除时，你的函数返回值就是一个悬垂引用或者指向已被删除的内存地址——这在C/C++里直接就是未定义行为。

dummy节点的本质是把一个可能变化的头节点问题，转化为一个恒定的头节点问题。你始终返回dummy.next，不管头节点被删了几次，这个返回值永远是当前链表真正的头。这是一个在任何链表操作中都值得养成的习惯，不只是在去重题里有效。

2.3 空间复杂度不是O(n)，而是O(值域范围)

很多人分析这个方案的空间复杂度时写“O(n)”，这是不严谨的。哈希集合的空间取决于不同值的个数，而不是链表的节点数。

如果链表节点值是int类型，其取值范围是2^32个可能值，哈希集合的规模是所有出现过的不同值的数量，最多不超过链表的节点数n，所以理论上界确实是O(n)。但如果链表节点值是字符串，并且这些字符串很长，那哈希集合的空间就是O(n × L)，其中L是平均字符串长度。这个区别在工程上很重要，因为如果字符串平均长度达到几百字节，哈希集合的内存开销很快就上去了。

另外，在C语言里没有现成的哈希集合可用，自己实现一个开放寻址法或者链地址法的哈希表，代码量会直接翻倍，还伴随着扩容、哈希冲突、删除标记等一堆问题。所以在工程实践中，如果需求空间确实可以放宽，我更倾向用C++的unordered_set，或者干脆用其他语言实现。

3. 空间受限时的出路：链表归并排序 + 一趟去重

如果面试官或者项目需求明确要求空间复杂度O(1)，哈希集合方案直接出局。这时候唯一现实可行的方法是：先把链表排好序，然后一趟扫描去重。

排序是O(n log n)，一趟去重是O(n)，总时间复杂度O(n log n)，空间O(1)。这是在“不允许额外空间”这个约束下能达到的最优解。

3.1 为什么单链表排序首选归并排序

数组排序时大家都会想到快速排序，但单链表上快排并不合适。快排的核心是随机访问和双向交换，单链表只能单向遍历，交换节点的代价非常高，而且快排在链表中很容易因为分割不均衡导致最坏情况O(n²)。

归并排序只需要递归分割和合并，天然适配了链表只能单向移动的特性。下面是链表归并排序的完整实现，注意找链表中间节点用的是快慢指针——快指针每次走两步，慢指针每次走一步，快指针走到尾时，慢指针正好到达中间：

struct ListNode* merge(struct ListNode* a, struct ListNode* b) { struct ListNode dummy; struct ListNode* tail = &dummy; while (a && b) { if (a->val <= b->val) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; } tail = tail->next; } tail->next = a ? a : b; return dummy.next; } struct ListNode* sortList(struct ListNode* head) { if (!head || !head->next) return head; struct ListNode *slow = head, *fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } struct ListNode* mid = slow->next; slow->next = NULL; struct ListNode* left = sortList(head); struct ListNode* right = sortList(mid); return merge(left, right); }

这个写的还是递归版归并排序，严格说空间复杂度是O(log n)，因为递归调用栈要占空间。如果要真正到达O(1)空间，要用自底向上的迭代归并排序，思想是先把链表切成大小为1的块，两两合并成大小为2的有序块，再合并成大小为4的有序块……直到整条链表有序。

3.2 排序后的去重，代码反而很简单

排好序之后，重复节点一定相邻，这个问题退化成有序链表去重。一趟扫描就能搞定，而且原地操作，不需要哈希表。

struct ListNode* deleteSortedDuplicates(struct ListNode* head) { if (!head) return NULL; struct ListNode* cur = head; while (cur && cur->next) { if (cur->val == cur->next->val) { struct ListNode* tmp = cur->next; cur->next = cur->next->next; free(tmp); } else { cur = cur->next; } } return head; }

这个循环里最容易被忽略的细节是：删除节点后，cur不前进，因为cur->next被更新成了一个新节点，这个新节点可能和cur->val还是重复的。这跟在数组里去重不太一样，数组里你只要维护一个写指针就行，链表里你得时刻意识到自己操作的是“指针的指针”。

4. 有序链表去重：双指针、边界条件与内存释放细节

上一节给出的有序链表去重代码在逻辑上是对的，但放到工程环境里，还是有一些值得展开的细节。这一节专门讲这些容易在真实代码中翻车的点。

4.1 为什么删除节点后cur不能直接往前挪

我见过很多次这种错误写法：

// 错误写法 while (cur && cur->next) { if (cur->val == cur->next->val) { struct ListNode* tmp = cur->next; cur->next = cur->next->next; free(tmp); cur = cur->next; // 错误！ } else { cur = cur->next; } }

问题在于：链表是1 -> 1 -> 1 -> 2这种三个连续重复的case，第一轮删除后，链表变成1 -> 1 -> 2，此时如果cur直接前进到第二个1，等于跳过了cur和第二个1的比较，最终结果是1 -> 1 -> 2，去重失败。正确做法是删除后cur保持不动，继续检查新的cur->next。

4.2 C/C++中的内存释放顺序：先保存，再释放

在C语言中删除链表节点，内存释放是一个绝对不能马虎的问题。标准操作是：先让前一个节点绕过要删除的节点，然后把要删除的节点free掉。但问题来了，free的是cur->next指向的那块内存，如果你在free之前就已经把cur->next覆盖成了cur->next->next，那被删除节点的地址就已经丢了。

所以上面代码里的顺序是：先把tmp指针指向要释放的节点，再更新cur->next，最后free(tmp)。这个顺序不能用free在前，否则你free之后再访问cur->next就是访问一块已经释放的内存，属于未定义行为。

C++里用delete同样要注意这个问题，而且在C++里更建议用智能指针管理链表节点，但如果你手写裸指针，上面的顺序依然适用。

4.3 边界条件测试清单

我建议所有写完链表代码的人都维护这样一份测试清单，至少跑一遍：

这些边界条件每个都能暴露一类典型的指针错误。比如“全部重复”的case，如果没有处理好删除后cur不前进的问题，最后一个节点就会残留。“空链表”case就不用说了，很多新手直接head->val取首个节点，空链表直接段错误。

5. 变体题与通用技巧：dummy节点和“删除全部重复”的写法

“删除重复节点”这个题最常见的变体，就是前文提到的：一旦发现某个值出现了重复，这个值的所有节点全部删除，一个都不留。这个变体在实际工作中也有对应场景——比如你要从一条事件链里剔除所有标记为异常的事件，异常事件可能连续出现多次，必须全部清掉。

5.1 “删除全部重复”的完整实现

这个需求的难点在于：头节点可能也是要删除的节点之一，而且删除一组重复节点后，新露出来的下一个节点可能又是重复组的起始点。处理方法是dummy节点加上“跳过整段重复区间”的策略：

struct ListNode* deleteAllDuplicates(struct ListNode* head) { struct ListNode dummy; dummy.next = head; struct ListNode* prev = &dummy; struct ListNode* cur = head; while (cur) { if (cur->next && cur->val == cur->next->val) { int dupVal = cur->val; while (cur && cur->val == dupVal) { struct ListNode* tmp = cur; cur = cur->next; free(tmp); } prev->next = cur; } else { prev = cur; cur = cur->next; } } return dummy.next; }

这段代码里有一个非常关键的细节：在跳过重复段的内部while循环里，prev始终没有动。只有把整段重复节点全部清掉、prev->next指向新节点之后，prev才在下一轮循环的条件分支里移动到当前位置。如果你在跳过重复段的循环体里就更新了prev，当重复段后面还有一段重复段时，链表的链接就乱了。

5.2 链表的三种基础操作是去重题的底层支撑

单链表的基本操作——遍历、插入、删除——是所有链表题的地基。去重题本质上是“遍历”和“删除”的组合。遍历要保证不丢节点，删除要保证不断链，这两个要求叠加在一起，就是前面反复强调的“先接链，再移动指针”、“删除时保存后继”、“释放节点前先取next”。

如果你对这三种基础操作还不够熟悉，建议先从最原始的实验题练起：实现一个单链表，支持头插、尾插、按值删除、按位置删除、遍历打印。把这几件事练到闭着眼都能写对，再回头看去重题，会觉得清晰很多。

5.3 其他高频变体一览

这个题还有几个常见变体，大家刷到的话可以顺手练一练：

• 删除链表中所有等于给定值的节点：比如删除所有值等于val的节点，这和“删除全部重复”的代码框架几乎一摸一样，只是不用比较“前后是否相等”，而是直接和固定值比较。
• 对无序链表去重并统计重复次数：需要哈希表同时记录值和出现次数，先统计一遍，再删第二遍，时间O(n)，空间O(n)。
• 两个有序链表合并去重：合并的同时去重，归并排序的merge函数加一个跳过重复值的判断即可。

这些变体看上去各不相同，但它们的内核高度一致：正确地维护prev指针、小心地处理“当前节点被删除后prev不能动”的场景、时刻警惕头节点变化的可能性。把母题吃透了，这些变体都能迎刃而解。

6. 数据规模视角下的方案选型：别让“理论最优”绑架工程决策

前面聊了哈希表方案、排序+去重方案、有序链表双指针方案，每个方案都有自己适合的场景。工程上选型不能只看复杂度表，还要看数据规模、运行环境、实现成本，甚至代码维护者的水平。这一节我把自己的选型经验整理出来。

6.1 三种主流方案的综合复杂度对比

这看起来是一张很标准的对比表，但工程里的真实情况往往更微妙。

6.2 数据规模上的真实差异：百节点和千万节点不是一回事

如果链表只有几百个节点，方案怎么选都不会有性能问题。但链表一旦到了百万甚至千万节点量级，哈希表方案的内存开销就很可观了——保存一千万个int，哈希集合的实际内存占用在几百MB级别，这在很多嵌入式环境或内存受限的服务里是不可接受的。

反过来，归并排序的O(n log n)看着比O(n)慢，但在千万节点量级，n log n大约等于 2.3×10⁷ 次比较，实际耗时也就是排序那一瞬间的事情，和哈希表建立过程中都有巨大的缓存压力相比，未必真的更慢。

这里还要提一个经常被忽视的问题：链表本身的缓存局部性非常差。数组相邻元素在内存中是连续的，遍历时缓存命中率极高；链表节点的内存往往分散在堆里的各个角落，每次访问都要跳来跳去。所以真正需要处理超大规模链表时，我更倾向于先评估“能不能转成数组操作”。

具体做法是：遍历链表，把节点的值或者节点本身放进数组，在数组里排序/去重，再重建链表。数组排序可以调用库函数（比如C的qsort或者C++的sort），实现成本极低。代价是O(n)的额外空间。如果空间允许，这是一条非常实用的路，代码比手写链表归并排序简单太多，而且实际运行速度往往更快。

6.3 接口设计：让链表去重函数成为可复用的工具

如果这个去重逻辑要在多个地方复用，接口设计也值得想一想。我习惯这样的函数签名：

struct ListNode* deleteDuplicates(struct ListNode* head, int mode);

mode为0时表示“保留一个副本”，为1时表示“全部删除”。内部先判断链表是否有序（这一步本身是O(n)的），再决定走哪条路线——有序就直接一趟扫描，无序且未启用额外空间就走排序路线，其余情况走哈希表路线。

这样设计的好处是调用方不关心内部算法，你后续要改进算法实现也不用改接口。对于C语言这种没有函数重载和垃圾回收的语言，额外注意在头文件里用注释写清楚：返回值永远是新的链表头，调用方负责接收，避免有人直接忽略返回值导致头节点丢失。

6.4 我的几个实操习惯

最后分享几个我自己写链表代码时一直在用的习惯，都是从各种事故里总结出来的：

边界条件先行。写函数体的第一行就是判断if (head == NULL)，然后再开始主逻辑。这个习惯让我少修了无数个空指针崩溃。

画图，尤其是三节点以上的链表演变图。我写任何一个涉及指针修改的链表操作，都会在草稿纸上画出节点在操作前后的连接关系，很多时候代码写不出来，但图一画就通了。

每次都跑边界用例。不管时间多紧，提交代码前至少跑一遍空链表、单节点、全部重复、重复在头、重复在尾这五个经典用例。这些用例已经在第4节的表格里列出来了，可以直接当模板用。

内存分配和释放的成对审查。用malloc的地方必然要问：这个节点在哪里释放？谁负责释放？如果函数返回后链表头变成了新节点，那我调用的地方拿到的指针是不是最新的？这些问题的答案都不确定的话，代码就不该提交。

回过来看“高效删除链表重复节点”这个题目，它的价值从来不在于那几道题本身，而在于它逼着你去梳理链表这类数据结构中最底层的操作逻辑：如何安全地修改指针、如何处理可能变化的头节点、如何在不同时空复杂度之间权衡。这些能力在做树、图乃至更复杂的数据结构时完全通用。把这个题做一遍，然后花时间把变体和边界全部跑通日，你对链表的理解会进入一个新的层次。