删除链表中的重复元素这题我在面试场合见过上百次也在实际业务代码里亲手写过好几个版本。看着就几行代码的事但真让你在白板上手写或者在你的课程实验里跑起来删除这两个字背后藏着的细节非常多有序还是无序、头节点会不会被删、空指针怎么防、内存要不要释放每一处都能单独拿出来问倒一片人。这篇文章我打算把链表的基本操作、遍历方式、以及有序和无序两种场景下的去重实现完整讲透每一步的为什么都给你说清楚。不管你是准备算法面试还是正在做单链表的基本操作实验照着这篇文章的思路和代码走基本不会翻车。1. 场景与需求拆解这道题到底在考什么1.1 题面背后删除操作的本质先统一题面。最常见的版本是给定一个升序排列的链表删除所有重复的元素使得每个元素只出现一次最后返回删除后的链表头。这个版本对应的就是大家熟知的LeetCode第83题。还有一个变体要求把重复的元素全部删掉一个都不留比如1 - 2 - 2 - 3要变成1 - 3这是第82题。很多人第一次拿到这题觉得不就是把值相等的节点删掉吗真上手才发现完全不是那么回事。链表的删除和数组的删除有着本质区别在数组里删除一个元素需要把所有后续元素往前移动所以数组去重常用双指针原地覆盖的思路而链表里删除一个节点不需要移动任何数据只需要把前一个节点的next指针重新指一下绕过待删除节点就行。听起来更简单但代价是——你必须找到前一个节点。这一句话就是整道题的核心。所以这道题表面在考去重实际上在考三样东西一是你对链表内存结构的理解二是你对遍历和前驱节点关系的把握三是对边界条件的敏感度。任何一个环节不扎实代码一跑就露馅。1.2 有序与无序两条完全不同的解题路径去重之前第一件事是看链表本身是否有序。这直接决定你用多复杂的算法有序链表重复元素一定相邻。你只需要一次遍历比较当前节点和下一个节点的值相等就删掉。时间复杂度可以做到 O(n)空间复杂度 O(1)原地完成。无序链表重复元素散落在链表各处你无法通过相邻比较来发现。要么用一个哈希表记录已经出现过的值要么用双重循环对每个节点往前面逐个查找。前者 O(n) 时间、O(n) 空间后者 O(n²) 时间、O(1) 空间。很多人拿到题不先问链表是有序的吗上来就写哈希其实丢了最基本的判断。我在实际项目里处理过一批历史数据当时情况就是链表本身按时间排序只是时间戳有重复这种情况一次遍历搞定完全不需要引入额外的存储。先判断数据形态再选算法这个习惯比背代码值钱得多。2. 链表操作的基本功动手前必须想清楚的几件事2.1 单链表的内存结构与指针关系只要是链表题段错误一多半出在对内存结构理解不到位。单链表的基本操作实验里第一步永远是定义节点结构。C语言里通常是这样的struct ListNode { int val; struct ListNode *next; };每个节点就是一块独立的内存里面存一个数据值val外加一个指针next指向下一块内存。链表的链就是靠这些指针一个个串起来的。最后一个节点的next必须置为NULL它是遍历时判断结束的标志。有些同学容易在这里犯迷糊struct ListNode *next存的是下一块内存的地址不是下一块内存的内容。这就像你拿着一张纸条纸条上写着下一个人的位置你要找下一个人得先看纸条然后跑到那个位置去。很多空指针访问本质上是纸条上什么都没写NULL你却硬要往那个位置跑。C里写链表除了结构体本身还要注意构造函数的写法这也是c结构体链表基本语法里常被问到的点struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };有构造函数之后new ListNode(5)就能直接生成一个值为5、next为空的节点比手动逐个赋值省事得多也不容易漏初始化。我见过很多C新手因为没写构造函数每次创建节点都要写三行赋值然后漏掉next nullptr后面遍历时程序直接崩。这种细节实验报告里老师也会盯着看。2.2 遍历、前驱节点与断链的关系链表的遍历是几乎所有操作的地基。最基本的遍历长这样struct ListNode *cur head; while (cur ! NULL) { // 访问 cur-val cur cur-next; }但删除操作和遍历有个关键区别当你站在某个节点上时你只能拿到它自己的值和它下一个节点的指针你拿不到前一个节点的指针。单向链表天生就是只能往后看不能往前看的结构。要删除某个节点唯一的方法是从前一个节点出发把它的next改掉。打个比方一列排队的人你想把队伍里的张三请走光跟张三说你走没用你得找到张三前面的李四让李四的手从搭在张三肩膀上改成搭到张三后面那个人的肩膀上。李四就是张三的前驱节点。这个类比想通了链表删除的所有代码逻辑就都顺了。于是就有了两种常见策略。一种是维护一个前驱指针prev让它始终走在当前节点的前一个位置另一种是用一个虚拟头节点dummy把空头、删头等特殊情况统一掉。这两种策略在后面去重代码里都会用到建议你先把它们的区别想明白再往下写。3. 有序链表去重双指针一次遍历的实现方案3.1 核心思路一次遍历原地删除回归最经典的场景升序链表重复元素相邻。思路其实非常直观从头部开始用cur指向当前节点检查cur-val和cur-next-val是否相等。相等说明cur-next是冗余节点把cur-next绕过它指向下下个节点不相等说明当前节点安全cur往前走一步。这里有个特别容易写错的点如果相等cur不能动。为什么因为你删掉一个重复节点之后新的cur-next可能还是和cur相等。比如链表是1 - 1 - 1 - 2你删掉第二个1之后cur还指向第一个1它的next变成了第三个1值还是相等的必须继续删。只有删到cur-next的值不等于cur了cur才能放心前进。很多人写成无论等不等cur都等于cur-next结果链表变成1 - 2肉眼看着对但过程其实是跳着删的逻辑上是个隐患。3.2 C语言完整实现与逐行讲解直接上代码这是LeetCode 83最标准的解法struct ListNode* deleteDuplicates(struct ListNode* head) { if (head NULL) { return NULL; } struct ListNode *cur head; while (cur-next ! NULL) { if (cur-val cur-next-val) { struct ListNode *tmp cur-next; cur-next cur-next-next; free(tmp); } else { cur cur-next; } } return head; }逐行拆开说第一开头判空。head NULL时直接返回NULL。这行不写后面cur-next就成了解引用空指针必崩。有人觉得判空多余实际面试里这恰恰是第一个加分点。第二循环条件是cur-next ! NULL而不是cur ! NULL。为什么因为你在循环体里要访问cur-next-val如果cur-next已经是空指针访问它的val就是空指针解引用。用cur-next ! NULL当条件能保证每次进循环体时cur-next都是合法节点。这也是链表题的常见边界处理技巧。第三tmp cur-next这一行非常关键。cur-next cur-next-next执行完之后原来的cur-next节点已经没有任何指针指向它了。如果你不提前用tmp把它记下来free就无从谈起这块内存就泄漏了。这也回答了很多人为什么不能直接free(cur-next)再改指针的疑问——先free再改你改的时候已经在访问一块已释放的内存行为未定义。第四else分支里cur cur-next。这个移动必须放else里原因开头讲过。你可以在纸上画一下1 - 1 - 1这个例子的执行过程画完就再也不会忘。3.3 Python实现与细节对比Python写链表去重逻辑和C完全一样只是不用管内存释放class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def delete_duplicates(head: ListNode) - ListNode: cur head while cur and cur.next: if cur.val cur.next.val: cur.next cur.next.next else: cur cur.next return head注意Python里while cur and cur.next这种写法利用了and短路的特性如果cur本来就是None后面的cur.next根本不会执行天然防空。我第一次用C语言习惯了看到这行代码愣了几秒后来才反应过来语言特性帮我们挡掉了一个if。C语言必须自己判空Python替你判了。还有一点C语言free(tmp)是在手动管理内存而Python的旧节点在失去引用之后会被垃圾回收机制自动处理所以你不需要del它。我见过一些从C转Python的同学写完了满脑子想着释放两个字憋了半天不知道该往哪放。其实这就是两种语言内存哲学的差异不是你的问题。3.4 变体重复元素全部删除的LeetCode 82第83题删完还留一个第82题是一个不留。如果你只背83的代码遇到82直接懵。82需要引入虚拟头节点dummy因为头节点本身也可能是重复值需要被删掉。没有dummy光处理头节点就要写一堆特判。struct ListNode* deleteDuplicates(struct ListNode* head) { struct ListNode dummy; dummy.next head; struct 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) { struct ListNode *tmp prev-next; prev-next tmp-next; free(tmp); } } else { prev prev-next; } } return dummy.next; }dummy节点不存储实际数据它的唯一作用就是让删除头节点和删除中间节点用同一套代码逻辑。内层那个while会一次性把所有值为dupVal的节点全部扫掉。注意内层while结束之后prev不能动。因为删完之后新的prev-next可能又带着别的重复值。这个思路和83的相等时cur不动是同一个道理——删除之后重新从当前角度审视后面的节点。3.5 与数组有序去重的对照理解热词里还出现了给定一个升序排列的数组原地删除重复出现的元素这其实就是LeetCode 26和链表版常常被拿来对比。数组版用快慢双指针int removeDuplicates(int* nums, int numsSize) { if (numsSize 0) return 0; int slow 0; for (int fast 1; fast numsSize; fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }数组的删除是覆盖slow指针表示最终保留元素的位置链表的删除是断链cur指针找到前驱然后绕过去。两者时间复杂度都是O(n)空间O(1)但操作方式完全不同。面试官让你先写数组版再写链表版就是测试你能不能把同一问题的两种存储结构解法分开。很多细节比如数组版里slow从0开始、返回slow1和链表版里cur从head开始、返回head都是各有各的道理不建议混着背理解内存结构之后自然就记住了。4. 无序链表去重哈希法与双重循环的取舍4.1 哈希表法空间换时间链表一旦无序相邻比较就失效了。最常见的做法是哈希表从前往后遍历把每个节点的值放到一个集合里如果当前节点的值已经在集合中出现过说明它是重复节点删掉否则加入集合并继续走。def delete_duplicates_unsorted(head: ListNode) - ListNode: dummy ListNode(0, head) seen set() 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的更新时机。你注意看删除重复节点的时候prev没有动只有cur往前走了只有在cur被确认不重复的时候prev才跟着cur前进。这和83里cur的移动逻辑如出一辙——被删节点的前驱不动这个原则从有序到无序从C到Python从来没有变过。那为什么这里要用dummy因为无序链表的头节点也可能是重复值啊。没有dummy你写prev时就得单独判断如果head重复了怎么办逻辑会变得很啰嗦。dummy一放头节点删除就和其他节点删除完全同构这段代码的prev永远有一个合法的前驱。这个技巧我建议直接焊死在脑子里所有可能删头的链表题都能用。C语言里实现哈希比较麻烦得自己撸一个哈希表或者用现成的第三方库所以C语言面试题一般不要求你写哈希去重能说出思路、用Python/Java写出来就够了。但如果你非要用C写暴力双重循环反而是更实在的方案。4.2 双重循环暴力法O(n²) 实战场暴力法的思路是对每个节点cur拿着它的值去它前面的所有节点里逐个比较看有没有出现过。因为链表只能往后走前面的节点需要每次从头开始找所以总代价是 O(n²)。C语言版本如下struct ListNode* deleteDuplicatesUnsorted(struct ListNode* head) { struct ListNode *cur head; struct ListNode *prev NULL; while (cur ! NULL) { struct ListNode *runner head; int dup 0; while (runner ! cur) { if (runner-val cur-val) { dup 1; break; } runner runner-next; } if (dup) { prev-next cur-next; free(cur); cur prev-next; } else { prev cur; cur cur-next; } } return head; }这段代码的坑点在于cur是第一个节点的时候runner从head出发runner ! cur是假的内层循环一次都不执行dup保持0说明头节点一定保留。这个行为是对的——第一个出现的元素永远不是重复的。但很多人在调试时看不懂为什么内层循环没进去其实这正是预期行为。另一个坑是prev的处理。当你删掉cur之后prev依然指向前一个节点同时cur prev-next指向被删节点的下一个节点这个顺序不能反。你如果先cur cur-next再prev-next cur就会丢掉前驱关系链表就断了。我当年写这段的时候栽过调试到凌晨两点最后发现就是两行代码顺序反了。链表的操作顺序优先级比语法还高。还有一个细节runner ! cur这个条件依赖cur自己在链表里。如果前面有节点被删除链表已经改过了但cur作为活节点仍然在链表中所以这个遍历是成立的。这也是用结构本身保证逻辑正确的思路写的时候要多想一步。4.3 两种方案的对比与选型建议无序链表去重的两条路做决定前最好心里有个对比表方案时间复杂度空间复杂度实现难度适用场景哈希表法O(n)O(n)低Python/Java中C需自建哈希数据量大追求速度内存不敏感双重循环O(n²)O(1)低逻辑直观链表很短或环境不允许用额外存储我的建议是课程实验和日常工作里链表节点就几百个双重循环写起来最快也最好解释反之如果链表有几万几十万个节点O(n²) 的代价会直接卡死你一定用哈希。数据量就是选型的唯一标尺别迷信最优算法也别鄙视暴力法。我常跟人说暴力法不是笨是在约束条件下最稳的选择。另外还有一个辅助思路如果你的链表可以随便重新组织先把链表转成数组排序去重再重建链表。这在允许改变原链表结构的场景下是可行的代码写起来也直观。缺点是额外空间和重建成本都不低实际用到的情况不多但面试里主动提一句如果允许重构链表我有另一种方案会显得你思路很开阔。5. 边界条件、常见问题与排查技巧5.1 必须处理的五个边界场景链表题的分数差距基本都体现在边界条件的处理上。去重题至少分五类输入每一类我都建议单独测试过再交代码输入场景期望输出关键风险空链表NULL返回NULL不判空直接解引用段错误只有一个节点1返回原链表循环条件写错导致越界全部重复1 - 1 - 1只剩一个节点1删除后cur未正确处理死循环或漏删头部重复1 - 1 - 21 - 283版不需要动head82版必须用dummy尾部重复1 - 2 - 21 - 2循环结束时cur-next为空容易多走一步无重复1 - 2 - 31 - 2 - 3不应改动任何指针我个人的习惯是先把这些用例写在草稿纸上再开始写代码。代码写完一行一行照着这些例子人肉跑一遍尤其是1 - 1 - 1这个极端例子能跑通说明你的删除循环逻辑基本是稳的。很多人觉得白板写代码手到擒来但链表的指针操作光靠脑子想是不行的手画箭头比什么都管用。5.2 实际调试中的翻车现场下面这几个问题我在带新人、包括自己刷题时都真实遇到过每条都是血泪教训空指针访问。症状是程序跑着跑着提示段错误Segmentation fault核心原因十有八九是你在cur-next为NULL时还去访问cur-next-val。解法就一句话所有下一个节点访问之前先确认cur-next不为空。这也是为什么要用while (cur-next ! NULL)而不是while (cur ! NULL)。死循环。写83时如果相等分支里画蛇添足地写了cur cur-next碰到1 - 1 - 1这种输入你会看到程序永远在删同一个节点因为cur根本没往前走。排查时先打印cur的值发现一直不变基本就是这个原因。记住删除动作发生的时候当前位置不移动这是原则。内存泄漏。C语言版漏了free(tmp)代码功能完全正常但跑久了内存蹭蹭涨。这种问题在OJ上不一定查得出来但实验报告或者代码审查里会被拎出来说。你可以在每次free之后把指针置NULL养成习惯后面排查悬垂指针也方便。释放野指针。有同学写free(cur)然后cur cur-next这里cur-next已经被释放了属于在已经扔掉的纸条上读地址行为完全不可预期。必须先保存下一个节点的地址或者先用prev-next指向下一个节点再free。顺序错了一切全错。使用未初始化的next。C/C里如果你用malloc或new创建节点但忘了给next赋值它可能是一个随机的野地址。遍历的时候程序会沿着这个野地址一路狂奔直到撞上不可访问的内存才停下来。所以每次创建节点第一件事就是把next置为NULL或nullptr。5.3 面试与实验报告中的加分细节如果你是在准备面试除了代码正确这几点能给你加分。第一写之前主动确认条件。链表是升序的吗重复元素要保留一份还是全部删掉可以修改原链表吗这几个问题一出口面试官就知道你见过这题而且有工程思维。实际问题里需求模糊到这种程度很常见不确认清楚就动手是新手最容易犯的错。第二写完代码主动说复杂度。83版时间复杂度O(n)空间O(1)无序哈希版时间O(n)、空间O(n)。一句话的事但很多人不说面试官就得追着问。主动讲清楚观感完全不一样。第三主动提边界情况。我需要先处理空链表和单节点另外这个解法的循环条件保证不会访问到空指针。这些话不需要很多但能证明你脑子里有一套完整的边界检查机制。如果你是做单链表的基本操作实验报告建议把创建链表、遍历、插入、删除这几个操作整合到一起写一个完整的测试程序先创建一个带重复元素的链表打印出来调用去重函数再打印结果。这样既展示了基本操作又展示了完整逻辑报告会漂亮很多。6. 从一道题看一类题链表的前驱思维才是根本去重题做完了我想再聊聊它背后的方法论。会做这一题不算什么能把它和一整类链表题串起来才是真的吃透了。你会发现无论是83的cur不动还是82的prev不动还是无序哈希版的prev在删除时不更新它们的核心都绕不开一个概念删除节点必须依赖前驱节点。这个前驱思维你把它记熟了后面做单链表的逆序、链表的插入、链表的排序全都用得上。比如python单链表逆序这个高频题本质上是每一次循环都修改当前节点的next指向它的前驱那个前驱指针就是这么一点点往前挪的。再比如链表插入操作你要在某个节点后面插一个新节点也要先通过前驱找到插入位置再处理next指针的先后顺序。说到底链表题就是指针操作的排列组合而前驱节点就是那条串联一切的主线。还有一个贯穿始终的判断标准在修改链表的指向之前一定要确认被绕过的节点是否已经被记录下来。这句话我说了不下十遍但每次看别人的代码还是能看到直接cur cur-next把原next搞丢的情况。链表的指针操作本质上是一个先记、再改、后删的过程顺序永远是记旧指针、改新指向、删旧节点。记住这个顺序你就躲开了链表题里一半的坑。另外说句实在话这种经典题不要只刷一遍。我今天写83、82、无序哈希、暴力法四个版本的代码合在一起你与其追求今天全背下来不如分三次来第一次理解83和82第二次写无序哈希第三次用C语言手写暴力版并盯着内存释放。每次重新写你会发现上次没注意到的细节。我在带实习生的时候总结过链表题的笔试淘汰率之所以高不是因为难而是因为太容易在细节上犯晕。你只有多练几次把那些想当然的细节变成肌肉记忆才算真正掌握了。最后送你一个我自己的测试习惯写完全部代码之后一定要在本地把它运行起来而不是盯着屏幕觉得应该没错。哪怕你只是写个20行的测试程序把链表创建、遍历、去重、再遍历串一遍也能帮你挡掉一半以上的低级错误。题是刷不完的但好习惯能让你每刷一道题都真正变成自己的能力。