链表删除重复节点：高效解法、代码实现与边界陷阱

链表的删除操作很多人在学校就学过但真到了面试或者实际项目里写出来的代码却总有几个隐藏问题要么内存泄漏要么空指针崩溃要么边界条件处理错了。尤其是“删除重复节点”这个题目看起来简单其实考查的点非常密集——你不仅要处理链表的遍历和断链还要设计高效的查重策略稍不注意就是O(n²)的暴力解法。我自己刷题和带新人的时候这个题目出现频率极高所以今天想好好把它拆开讲透。这篇文章会覆盖链表删除的底层原理、四个不同场景的去重方案、可运行的C语言和Python代码、以及我实际踩过的那些内存和边界坑。适合正在学数据结构的初学者、准备算法面试的求职者以及工作中需要手写链表的工程师参考。1. 先搞清楚这个题目在问什么1.1 需求拆解什么叫“高效”标题里“高效”两个字其实是整个题目的关键。很多人一上来就写两层循环外层遍历每个节点内层再扫描一遍找重复值然后把重复节点删掉。这种写法能跑通但时间复杂度是O(n²)数据量一上来就完蛋。所谓高效至少要分两个维度看时间复杂度和空间复杂度。常规的优化思路是用哈希表把查重从线性扫描变成O(1)判断这样一次遍历就能完成时间复杂度降到O(n)代价是需要额外的O(n)空间。如果题目要求原地操作、不能用额外空间那就必须先排序链表再相邻比较去重此时时间复杂度是O(nlogn)。所以拿到题目第一件事不是写代码而是问清楚约束条件链表是有序还是无序允不允许用额外空间重复节点是保留一个还是全删这几个问题的答案直接决定方案选型。我这里按常见面试场景整理了四个方案后面每一节都会对应一个。1.2 为什么链表删除节点比数组麻烦数组删除一个元素只要把后面的元素往前挪就行逻辑很直观。链表不一样它的节点在内存里是散落的通过指针串联。删除链表节点本质是两件事让前一个节点的next跳过当前节点指向下一个节点然后释放当前节点的内存如果用C/C。麻烦就麻烦在“让前一个节点知道要跳过当前节点”这个动作。链表只有next指针没有prev指针单链表所以你在遍历的时候必须维护一个“前驱指针”否则一旦走到当前节点就再也找不到它前面的那个节点了。很多新手写删除逻辑时总是报错根因就是这个没有维护prev或者维护错了prev的位置。另外还有一个容易忽略的点如果删除的是头节点那么链表的头指针本身要更新如果删除的是尾节点前驱节点的next要置NULL。这两种边界情况在有序链表的“重复节点全删”方案里尤其常见后面我会在代码里演示。2. 前置基础链表的结构与基本操作2.1 单链表节点的定义以C语言为例最常见的节点定义长这样typedef struct ListNode { int val; struct ListNode *next; } ListNode;字段就两个一个存数据val一个存下一个节点的地址next。别看它简单很多问题都出在next指针的操作上。举个生活化的类比链表就像一列火车每节车厢知道下一节是谁但不知道自己前一节是谁。如果你要让中间某节车厢脱离编组你必须让前一节车厢的挂钩改接到后一节车厢上同时把脱离的车厢拖去检修释放内存。有些教材会加一个头节点dummy node也就是链表第一个节点不存实际数据只作为入口。这个设计在删除场景里很有用因为头节点不存在“前驱为空”的问题统一了代码逻辑。后面讲“重复节点全删”时会专门用这个技巧。2.2 带头节点与不带头节点不带头节点的链表头指针直接指向第一个数据节点。删除第一个节点时必须修改头指针本身所以函数参数往往是二级指针ListNode **head或者让函数返回新的头节点。很多初学者用一级指针传头节点进去删除头节点后发现外面还是指向旧地址这就是典型的C语言指针传参问题。带头节点的链表头指针永远指向一个固定的哑节点它的next才指向第一个数据节点。这样删除第一个数据节点时只需要改头节点的next不需要动头指针本身代码写起来统一很多。我个人在做算法题时几乎总是使用哑节点技巧不为别的就为少写两个if分支。2.3 删除节点的三种姿势删除第i个节点代码模板是这样的// 已知prev是待删除节点的前驱 ListNode *toDelete prev-next; prev-next toDelete-next; free(toDelete);注意顺序先把toDelete的next保存到prev的next再释放toDelete。如果先free再赋值toDelete-next就变成野指针访问了这是C/C里最经典的错误。删除指定值的节点一般要遍历链表找前驱。删除倒数第k个节点则用双指针快慢指针技巧先让快指针走k步。这个题目虽然不是“删除倒数第k个节点”但这里的前驱维护逻辑是完全通用的。还有一种是删除当前节点但不给前驱已知只能访问当前节点——经典的“狸猫换太子”解法把当前节点的值改成下一个节点的值然后删除下一个节点。这个解法很巧妙但面试题里很少让你用而且如果当前节点是尾节点就失效了需要特殊处理。3. 核心方案逐个拆解3.1 方案一哈希集合辅助去重无序链表通用这是最通用、最好写的方案也是面试时我最推荐的“保底”方案。思路非常直接遍历链表用一个哈希集合记录已经出现过的值每到一个新节点先看它的值是否在集合里如果在说明是重复节点删除它如果不在把值加入集合继续往下走。这个方案不管链表是否有序都能用而且代码量小逻辑清晰。时间复杂度O(n)空间复杂度O(n)。LintCode原题删除排序链表中的重复元素虽然是有序链表但用这个方案一样能过只是没能利用有序这个条件进一步省空间。用Python写的话哈希集合就是set()天然支持。C语言实现则需要自己拉一个哈希表稍微麻烦一点。不过面试场景下如果允许额外空间我用Python直接set()就完事了C语言的话我一般会先问面试官“能不能用辅助空间”如果允许直接上最简单的数组计数前提是数值范围已知且不大或者自己写个小哈希。3.2 方案二有序链表原地去重重复节点保留一个如果链表本身是有序的那问题会变得非常简单不需要哈希集合只要一次遍历就能完成去重。原理不复杂因为链表有序所以相同的值一定连续排列。你用cur指向当前节点如果cur-next存在且cur-next的值和cur相同说明遇到重复了删除cur-next如果不同cur指针往后挪。这里有个细节值得强调图片经常有人写错——当删除完一个重复节点后cur不应该立刻往后移因为cur-next可能后面还有连续重复的值。正确做法是发生删除时cur不动继续检查新的cur-next只有没发生删除时cur才往前走。这个逻辑和“删除排序数组的所有重复元素”里的双指针是同一个思想只不过链表天然省去了搬移元素的麻烦。这个方案的代码很短而且是真正的“原地”空间复杂度O(1)时间复杂度O(n)。如果题目明确说“链表已排序”这就是最优解。3.3 方案三有序链表去重重复节点一个不留很多面试题会在这里加难度不是保留一个重复值而是把重复的节点全部删掉一个都不留。比如1-2-3-3-4会变成1-2-4中间的3都没了。这个变种立刻就把很多人的代码打回原形因为头节点可能就是重复节点比如1-1-2-3需要删掉两个1头指针要换位置。解决办法就是前面提到的哑节点。创建一个dummy节点dummy-next指向head用一个prev指针初始指向dummy。遍历时如果发现prev-next和prev-next-next的值相等就记录这个重复值然后不断删除prev-next直到prev-next为空或者值不等于重复值如果不相等prev才往前移。这里最反直觉的点是当删除了一堆重复节点后prev也不能急着往后挪因为新的prev-next可能还是重复值比如1-2-2-2-3-3删完2之后新的prev指向1此时1-next指向3前面的3和后面的3还是重复。所以必须继续循环判断。这个细节能当场写对的考生说实话不多因为它考察的是“循环不变量”的思维——每次循环结束后prev-next要么为空要么是一个“暂时无重复”的节点但仍然需要下一轮验证。3.4 方案四暴力双重循环原理理解但别用于生产还有一些教科书会把暴力法写出来作为“最朴素思路”的引入。外层循环固定一个节点cur内层循环从cur的下一个节点开始逐个比较值遇到相等的就删除。但这里有个性能上的大坑内层的删除是O(n)的操作套上外层遍历就是O(n²)。如果链表有10万个节点这个算法要跑大约50亿次比较肉眼可见地卡死。暴力法唯一的优点是空间复杂度O(1)且不要求链表有序。但在工程里几乎不会用面试时如果你只给出这个解法大概率会被追问“能不能优化”。所以我的意见是理解原理能用来解释“为什么不能这样写”就够了真正面试手撕代码别选它。4. 完整可运行代码与测试场景4.1 C语言完整实现下面这段是我在LeetCode风格环境下常用的C语言版本针对“有序链表重复节点保留一个”的写法#include stdio.h #include stdlib.h typedef struct ListNode { int val; struct ListNode *next; } ListNode; ListNode* deleteDuplicatesKeepOne(ListNode* head) { if (head NULL) return NULL; ListNode *cur head; while (cur ! NULL cur-next ! NULL) { if (cur-val cur-next-val) { ListNode *dup cur-next; cur-next dup-next; free(dup); } else { cur cur-next; } } return head; }注意看第9行的if/else结构值相等时只更新cur-next不移动cur值不等时才移动cur。这个写法能正确处理连续多个重复的情况比如1-1-1-2三次循环中cur始终指向第一个1直到把所有1都删完cur才移动到2。如果是“重复节点一个不留”的版本代码如下ListNode* deleteDuplicatesRemoveAll(ListNode* head) { ListNode dummy; dummy.next head; ListNode *prev dummy; while (prev-next ! NULL prev-next-next ! NULL) { if (prev-next-val prev-next-next-val) { int dupVal prev-next-val; while (prev-next ! NULL prev-next-val dupVal) { ListNode *tmp prev-next; prev-next tmp-next; free(tmp); } } else { prev prev-next; } } return dummy.next; }这里我直接用栈上变量dummy而不是malloc一个dummy节点就是图省事不用释放。dummy.next在函数结束时就是新链表的头指针。注意dummy.next初始指向head即使head被删掉dummy.next也会跟着被更新这就是哑节点最大的好处。使用“重复节点保留一个”版本的完整测试程序构造链表1-1-2-3-3调用函数后再打印链表预期输出1-2-3。一定要把打印逻辑放到一个单独函数里用循环遍历输出每个节点的值并且输出后要写一个释放函数释放链表所有节点否则跑一次就内存泄漏十几字节。虽少但堆积起来就是问题。4.2 Python版本对比Python的链表节点定义一般是这样class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def delete_duplicates_keep_one(head): cur head while cur and cur.next: if cur.val cur.next.val: cur.next cur.next.next else: cur cur.next return headPython没有指针和内存释放的概念cur.next cur.next.next实际上就让原来的cur.next节点变成“不可达”对象交给垃圾回收处理。所以在Python里写链表删除比C语言省心太多——不用管free也不用担心野指针。但也正因如此Python版本特别容易让人忽略“删除后cur不移动”这个关键逻辑写代码时还是要清醒。要是用哈希集合版本Python可以这样写def delete_duplicates_unsorted(head): seen set() dummy ListNode(0, head) prev dummy cur 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和cur两个指针cur负责往前走prev负责串联非重复节点。当cur重复时prev不更新当cur不重复时prev先指向curcur再往后走。这个写法能统一处理头节点重复的情况因为dummy兜底了。其实用Python做算法题时set是“神器”但也别滥用——如果面试官明确要求O(1)空间这个方案就不合格了必须换回方案二。4.3 测试用例怎么设计关于测试链表代码我吃过不少亏。很多人写完函数就测一个正例输出对了就觉得完事结果一上线上就崩。链表问题最怕的是边界用例所以我一般会准备这样几个case空链表head为NULL函数要直接返回不能报错单节点链表只有一个节点没有next的访问不能有野指针操作全部节点都是重复值比如1-1-1去重后应只剩一个1或全删看题目要求头节点和后面连续重复比如1-1-2必须确认新链表的头指对了没有重复节点的正常链表比如1-2-3遍历逻辑不能破坏原链表长链表的性能测试构造10万个节点的有序链表跑一遍看耗时建议把测试用例和输出函数封装好每次改动代码后跑一遍全套用例。这个习惯会给你省下大量排查问题的时间我自己的链表代码基本就靠这一套用例保证正确性。5. 实操中躲不开的坑5.1 内存管理free的时机C语言版本里节点是用malloc创建的删除时就必须用free释放。这个“必须”不是建议是强制。但free的时机如果搞错了会比不free更严重free之后再通过next指针去访问这个节点就是典型的“野指针解引用”轻则读到垃圾值重则段错误崩溃。我见过一个非常经典的错误写法删除节点后继续用cur指针访问它的next。因为cur已经被free了cur-next的行为是未定义的。正确做法是在free之前先把下一跳地址记下来。比如ListNode *nextNode delNode-next; free(delNode); cur nextNode; // 或者用别的变量保存很多现代静态检查工具和编译器比如AddressSanitizer都能查出这类问题所以我的建议是写C代码时就养成“先备份next再free”的肌肉记忆。面试时候如果考官问你“为什么这段代码不会野指针”你能说出这个思路印象分会高不少。另一个常见问题是拆分步骤写太长导致在if和else分支里各自处理了一遍next指针的更新结果某个分支忘了处理内存。这属于代码结构问题我的习惯是每个删除操作尽量收敛成一个小函数或一个固定代码块不要散落在多个分支里。5.2 尾节点和头节点的边界尾节点的特征是next为NULL。在删除重复节点时如果你不对next是否为NULL做判断就访问next-val那肯定崩。尤其注意while循环的终止条件比如“重复节点保留一个”如果写成while (cur) { if (cur-val cur-next-val) ... }在cur是最后一个节点时cur-next已经NULL了访问cur-next-val直接越界。头节点的边界问题在“一个不留”的方案里也容易出现。不用哑节点的时候如果头节点本身是重复节点你得把head往后移动移动完还要担心是否还有连续重复。用哑节点之后这个逻辑就从“手动改头指针”变成了“统一改prev-next”大脑负担小很多。这里说了这么多实际上就是想强调一句链表的调试大多数时间不是在调“算法”而是在调“指针是否为空”和“释放顺序是否正确”。你只要心里始终有这两个变量代码的稳定性能上一个台阶。5.3 面试场景下的思路表达如果你是在面试中遇到这个题我想多说一点因为代码正确只是一部分。很多候选人上来就闷头写写完给面试官一看如果思路有问题就尴尬了。我已经面试过不少人最稳定的答题节奏是先和面试官确认题目约束是否有序、是否允许额外空间、重复节点保留策略然后说出你的方案和复杂度最后再动手写。比如你打算用哈希集合可以这样说“我准备用一次遍历加一个哈希表时间O(n)、空间O(n)适合题目没有限制辅助空间的情况。如果限制空间我再改成先排序再原地去重。”这样既展现了你能分析多种方案又展示了你在权衡取舍时不是背答案而是真的理解了每种做法为什么好、为什么不好。说到这其实还有个小技巧如果你要在白板上写代码先把节点结构体写完再写主函数最后写测试用例。我见过有人连结构体都没写就开始写函数签名这种错误的代价是后面所有的代码都要返工浪费时间是小事给面试官的印象才是大问题。最后一个实战经验写完代码后一定要手动走一遍示例。拿支笔在纸上画出链表的每个节点和指针的指向变化逐行比对代码。这种走查方式虽然原始但是找出指针类bug特别有效。很多我看上去“很稳”的代码走一遍纸面就会发现index越界尤其是指针偏移的循环里。这个题目本身不难难的是把每一步都做到位。从理解需求、设计算法、写代码、释放内存、测试复核整个流程走通你对链表的掌握基本就到“及格线以上”了。以后遇到链表的其他变体题比如反转链表、合并有序链表、找中间节点都能复用这套分析方法和边界处理意识。我个人的体会是链表这一类题目与其刷很多道不如把一道小题彻底吃透把每个细节抠明白收获会大得多。