刷力扣的链表专题时有一类题特别能检验你对指针操作的掌握程度——删除排序链表中的重复元素 II也就是力扣第82题。题目一句话就能讲清楚给定一个已排序的链表删除原始链表中所有重复数字的节点只留下出现一次的数字对应的节点。但真到你动手去写代码的时候才会发现所谓“简单”的链表题难点永远不在思路而在边界条件和指针细节。这道题我前前后后刷过几遍每次都能发现新的理解盲区所以把完整解题过程、代码实现和踩过的坑整理出来给正在刷链表题的朋友一份可以照着走的参考答案。1. 这道题到底在考什么先看清题意再动手1.1 题目拆解和83题的核心区别力扣的链表系列里83题“删除排序链表中的重复元素”和82题经常被放在一起对比。83题的要求是“每个值只保留一个”也就是说重复的节点删除后还要留一个链表最终变成每个数字只出现一次。而82题“删除排序链表中的重复元素 II”是删除原始链表中所有重复数字的节点注意是“所有”用大白话说就是只要这个值出现过不止一次那就一个都不留。举个例子。链表1 - 2 - 3 - 3 - 4 - 4 - 583题的结果是1 - 2 - 3 - 4 - 582题的结果是1 - 2 - 5。仔细想想3 和 4 都出现了两次所以在82题里它们整个被删掉只有出现一次的 1、2、5 被保留。这个差异直接影响了代码写法也决定了82题比83题麻烦得多。83题只需要用一个 cur 指针一路走碰到cur.val cur.next.val就跳过一个节点属于“留一个”的经典去重思路。82题要删除一整段重复区间而且头节点可能正好落在重复区间内导致链表头部整体被删。“排序链表”在这里是一个非常重要的前提条件。因为链表是有序的所以相同的数字必然连续排列不会出现1 - 2 - 1这种相同值被隔开的局面。这个性质决定了我们只需要在相邻节点之间比较值就能确定某一段区间是否应该全部删除。如果你拿到的是一个未排序的链表相邻比较的思路立刻失效那就得换一套方案这个扩展我在第4章会提到。1.2 边界条件分析做题先想边界这是刷链表题必备的习惯。链表题的边界无非几种空链表、单节点链表、头部重复、尾部重复、全部重复。在这道题里每一种情况都对代码的正确性提出了要求。先把预期输出整理成表格写代码前做到心里有数输入链表预期输出注意点nullnull空链表直接返回1 - 2 - 31 - 2 - 3无重复原样返回1 - 1 - 1 - 2 - 32 - 3头部三个重复节点全部删掉1 - 2 - 3 - 3 - 31 - 2尾部重复节点删干净1 - 1 - 2 - 2null全部重复结果为空链表我第一次做这道题时就把“头部重复”这个边界给忽略了。当时直接拿 head 当遍历起点结果遇到1 - 1 - 1 - 2 - 3这种输入由于 head 自己就是重复节点在原来的遍历框架里没有任何一个节点的 next 指向 head 之前的节点也就无从把它从链表中摘除。代码跑完以后输出变成了1 - 2 - 3三个1里有两个被删掉剩下的头节点却顽固地残留了下来。这个错误几乎是所有初做者的共同经历。应对办法说来也简单核心就是四个字虚拟头节点。在真正的头节点前面再挂一个 dummy 节点让dummy.next指向 head然后所有删除操作都在 dummy 之后进行。这样即使原来的 head 被删除我们也有明确的新链表入口最终返回dummy.next即可。这个问题第2章重点展开。2. 核心解题思路虚拟头节点与逐段跳过2.1 为什么要用虚拟头节点力扣题中给出的链表头节点 head本身就是一个存了真实值的节点。在数据结构教科书里链表有两种常见形态带头结点的单链表和不带头结点的单链表。带头结点的链表会有一个不存业务数据的哨兵节点所有插入删除都在这个哨兵之后操作而不带头结点的链表head 直接就是第一个有效节点删除第一个节点时需要移动 head 指针本身。力扣的链表结构默认是不带头结点的这也是为什么很多链表增删题都要额外引入 dummy 节点的原因。有人可能会问直接用 head 指针不行吗比如检测到头部重复时就head head-next。理论上可行但实际操作会非常别扭。原因有两个第一head 的移动时机和后续遍历位置难以统一管理代码里会产生大量 if 分支第二还有一种场景是头节点本身不重复但第二个和第三个节点重复比如1 - 2 - 2 - 3这时候头节点必须保留遍历起点又确实需要从某个中间位置开始。各种分支混在一起代码写出来基本就是一团乱麻。dummy 节点的作用可以用一个生活类比来理解你在拆除一栋楼时会在楼外面搭一个脚手架脚手架本身不参与建筑业务只是让拆除工作能够稳定推进。dummy 就是那个脚手架它本身不是链表的有效节点不参与任何业务判断但它让“删除第一个节点”变成“删除第二个节点”这种常规操作从而让每一步都统一。代码结构上虚拟头节点的初始化很简单创建节点dummy令dummy.next head用一个指针 cur 从 dummy 开始移动所有判断围绕cur.next和cur.next.next展开最后返回dummy.next作为新的链表头。这么做还有一个额外好处如果链表被全部删空dummy.next会被置为 NULL返回它正好是空链表逻辑上非常干净不用单独判断“链表是否被删光了”。2.2 遍历逻辑两个关键的循环整个遍历过程可以用一句话描述清楚只要cur.next和cur.next.next都存在就判断它们的值是否相等如果相等就找到所有值相等的节点一次性全部跳过如果不相等cur 正常往前走一步。但为什么这里需要两层循环而不是一个 if 就能解决因为外层只负责“发现”重复真正“清除”一整段重复区间要靠内层循环。内层循环的必要性来自一个现实重复区间的长度是未知的。外层 while 判断cur.next.val cur.next.next.val只说明“至少有两个相邻节点相等”但这段重复区间可能是 2 个、3 个、甚至 10 个节点。要一口气把整段删光就必须先把重复的值记录下来比如记为 x然后不断执行cur.next cur.next.next把凡是值等于 x 的节点全部跳过。这个操作的数量不确定所以必须用 while 而不是 if。我见过一种替代写法第一遍扫描把所有出现次数大于1的值存进哈希集合第二遍扫描删除值为这些元素的节点。这种写法思路直白、很符合直觉在未排序链表上确实是最自然的方案。但在这道题里属于“杀鸡用牛刀”空间复杂度从 O(1) 直接变成 O(n)。面试时如果给出哈希集合方案面试官很可能会追问“能不能不用哈希集合”所以双循环的原地扫描方案才是标准答案。2.3 为什么每个节点最多访问两三次复杂度并不高有人看到嵌套循环就条件反射地认为是 O(n^2)这道题完全不是。我们以链表1 - 2 - 2 - 2 - 3 - 4为例走一遍cur 先指向 dummy比较节点1和节点2的值不相等cur 前进到节点1在节点1处比较第一个2和第二个2的值相等记录 x2内层循环把连续三个2全部从链表中摘掉内层循环结束后cur 仍停在节点1的位置但cur.next已经变成节点3再比较节点3和节点4的值不相等cur 前进到节点3进入下一轮。观察这个流程三个2虽然被多次比较但每一次比较都对应“确认一个节点是否该删除”的必要操作。如果把删除节点也算进访问次数每个节点被访问的次数是常数级不存在某段节点被反复扫描多遍的情况所以总复杂度是 O(n)。我单独把复杂度拿出来讲是因为初学者很容易在分析指针循环时晕掉把“有嵌套循环”误判成“平方复杂度”。面试中面试官非常看重你对自己代码复杂度的理解能讲清楚“为什么嵌套循环仍然是 O(n)”这本身就是加分项。3. 多语言代码实现一份思路三种写法3.1 C 实现与逐行解读C 版本可以说是这道题的“正典”因为指针操作在C里表达得最直接。完整代码如下class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* dummy new ListNode(0, head); ListNode* cur dummy; while (cur-next ! nullptr cur-next-next ! nullptr) { if (cur-next-val cur-next-next-val) { int x cur-next-val; while (cur-next ! nullptr cur-next-val x) { cur-next cur-next-next; } } else { cur cur-next; } } return dummy-next; } };逐行说几个关键点。第一dummy 的初始化。我用的是 C 里带两个参数的构造函数ListNode(0, head)表示 dummy 的值为0next 指向 head。这个0本身无关紧要因为 dummy 不会被业务逻辑读取。如果你的刷题环境不支持带两个参数的构造函数可以分开写ListNode* dummy new ListNode(0); dummy-next head;第二外层 while 的判断条件。cur-next ! nullptr和cur-next-next ! nullptr两个条件缺一不可顺序也不能互换。如果cur-next本身为空再访问cur-next-next就是空指针解引用程序直接崩溃。必须先判断前者再判断后者利用短路求值避免越界访问。第三内层循环删除节点时我直接写cur-next cur-next-next效果是“跳过当前要删除的节点”。在真实工程里如果节点是 new 出来的跳过的节点要考虑释放内存。力扣判题环境默认不要求手动 delete但如果是嵌入式开发或者C项目这里应该补上释放逻辑ListNode* tmp cur-next; cur-next cur-next-next; delete tmp;这也是嵌入式链表题目经常考察的细节链表节点删除背后是内存管理而不是简单的指针赋值。刷题和真实开发的差距往往就差在这些地方。3.2 Java 实现与逐行解读Java 版本和 C 的逻辑几乎完全一致区别只在于语言特性带来的语法差异。代码如下class Solution { public ListNode deleteDuplicates(ListNode head) { if (head null || head.next null) { return head; } ListNode dummy new ListNode(0); dummy.next head; ListNode cur dummy; while (cur.next ! null cur.next.next ! null) { if (cur.next.val cur.next.next.val) { int x cur.next.val; while (cur.next ! null cur.next.val x) { cur.next cur.next.next; } } else { cur cur.next; } } return dummy.next; } }Java 里的 ListNode 对象本质是引用类型cur.next cur.next.next这句话在内存里的语义和 C 指针非常接近都是“让当前节点的 next 指向下下个节点”。区别在于被跳过的对象如果没有其他引用指向它会被 JVM 的垃圾回收机制自动回收程序员不需要手动释放。还有一个细节值得提醒new ListNode(0)创建的 dummy 对象在判题环境里不会造成内存问题因为每个测试用例运行结束后虚拟机会回收没有实际引用的对象。你真正需要警惕的是逻辑错误导致链表成环——一旦链表出现环判题程序就会陷入死循环然后超时这种错误比内存泄漏隐蔽得多。3.3 Python 实现与逐行解读Python 的实现同样基于完全相同的思路代码更短但初学者容易疑惑“Python 也有指针吗”。其实 Python 没有传统意义上的指针但对象引用本质上就是一种指针。链表的每个节点都是一个对象节点之间通过next字段串起来这和一串盒子用绳子连接是同一个模型。class Solution: def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]: if not head or not head.next: return head dummy ListNode(0, head) cur dummy while cur.next and cur.next.next: if cur.next.val cur.next.next.val: x cur.next.val while cur.next and cur.next.val x: cur.next cur.next.next else: cur cur.next return dummy.nextPython 版本要注意的是while cur.next and cur.next.next这行。Python 的 and 也是短路逻辑如果cur.next是 None整个条件表达式立即结束不会执行后面的cur.next.next因此不会抛出AttributeError。这个特性和 C 的空指针检查在语义上是等价的但写法更简练。如果你是 C 或 C 转过来刷题的可能会觉得 Python 的链表缺少“指针的仪式感”这反而不利于理解指针移动的过程。我的建议是不管用什么语言遇到链表题先在纸上手动模拟一遍指针移动把 cur、dummy、重复区间的位置都标出来再落代码。画图熟练了代码写起来基本一遍过。3.4 递归解法另一种实现方式迭代法是本题的主流解法但递归在面试中也经常被要求手写所以有必要掌握。递归的核心逻辑是如果 head 和 head.next 的值相等就跳到第一个值不相等的节点递归处理后续部分如果 head 和 head.next 的值不相等则保留 head并把 head.next 设置为递归处理的结果。C 递归代码如下class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } if (head-val ! head-next-val) { head-next deleteDuplicates(head-next); return head; } ListNode* p head; while (p ! nullptr p-val head-val) { p p-next; } return deleteDuplicates(p); } };递归解法最需要理解的是每一层的返回值。如果head-val ! head-next-val说明 head 是要保留的它的后继由递归结果决定返回 head。如果值相同则 head 这一整段都不要用 p 指针把相同节点全部跳过然后从第一个不相等的节点开始递归。p 指针跳过的动作保证了重复节点不会残留。递归的时间复杂度仍然是 O(n)但空间复杂度是 O(n)因为递归需要占用调用栈空间。对于力扣的链表长度栈深度通常不会爆但面试时如果被问到空间复杂度必须明确说出迭代是 O(1)、递归是 O(n) 这个区别。很多面试官喜欢让你先写递归再改写成迭代目的就是考察你对递归栈的理解。4. 复杂度细节、常见错误与变种扩展4.1 时间与空间复杂度分析这道题的最优解是迭代法时间复杂度和空间复杂度都需要明确。时间方面外层 while 循环每轮要么删除节点要么让 cur 前进一步。删除重复段时内层循环会连续跳过多个相同节点但每个节点只会被跳过一次不会重复进入外层循环的判断流程。极端情况如1 - 1 - 1 - 1 - 1这种全是重复节点的链表内层循环会一口气把五个1全部删完之后cur-next变成 NULL外层循环退出。整个过程每个节点只被访问常数次总时间复杂度 O(n)n 是节点总数。空间方面迭代法只新建了一个 dummy 节点和若干临时指针变量辅助空间是 O(1)这是它优于哈希集合方案的关键点。之前提到的哈希集合方案空间复杂度 O(n)对于这道排序链表的场景属于过度设计。如果你在面试中主动提到“这里可以用哈希集合但排序链表场景下不需要”反而能展示出你对比特性和场景的思考深度。4.2 常见错误与排查技巧实录刷这道题的过程中我总结出几个高频错误整理成速查表对照排错非常方便错误类型具体表现原因解决办法空指针异常访问cur.next.next时报错没判断cur.next为空while 条件先判空再访问头节点残留1 - 1 - 2输出1 - 2没有虚拟头节点使用 dummy 节点重复区间未删干净1 - 2 - 2 - 2 - 3输出1 - 2 - 3内层只删了一个节点用 while 把所有等于 x 的节点删光死循环程序运行超时cur 没有前进或链表意外成环每轮要么删节点要么 cur 前进误删该保留的节点相邻重复段漏删删除后 cur 错误地向前移动删完重复段后 cur 原地不动两个坑值得单独展开。第一空指针判断的书写顺序。很多初学者先写while (cur-next-next ! nullptr)补上cur-next的判断时又把顺序写反变成while (cur-next-next ! nullptr cur-next ! nullptr)照样崩溃。原因就在于短路求值你必须让可能为空的表达式靠前。标准写法就是cur-next ! nullptr cur-next-next ! nullptr这个顺序建议直接记死每次写链表循环都条件反射地先想到“判空在前”。第二删除节点后 cur 到底要不要移动。这个问题我见过很多人纠结。结论是在“删除重复段”的分支里cur 不能移动。因为跳完一段重复区间后新的cur.next可能是下一段重复区间的开头需要继续在这个位置检查。比如1 - 2 - 2 - 3 - 3 - 4删完两个2之后cur.next 变成了第一个3而3也是重复值只有 cur 原地不动才能在下一轮里继续发现3的重复性。如果删完重复段就让 cur 前进一步就会漏删“紧挨着的第二段重复值”。再分享一个调试技巧。链表题调试最痛苦的是节点关系一变链表结构肉眼完全看不出来不知道断点断在哪里。我的习惯是写一个带计数上限的打印函数void printList(ListNode* head) { ListNode* p head; int cnt 0; while (p ! nullptr cnt 20) { std::cout p-val - ; p p-next; cnt; } std::cout NULL std::endl; }计数器 cnt 是防止链表意外成环时无限打印。每次删完一段重复区间就把当前链表打印出来看从哪个节点开始结构不对。这种临时调试代码虽然不能留在提交版本里但排查逻辑错误时远比盯着代码空想高效。4.3 变种问题与实战扩展一道题刷完如果只满足于通过用例收获就太小了。我建议把82题和几个相关变种放在一起分析形成一张“链表去重家族”的知识网。第一个变种是83题保留一个重复元素。顺着前面的思路83题的解法简单很多如果cur.val cur.next.val就删掉 cur.next否则 cur 前进最终每个值只保留一个。数学上可以理解为 82 题是严格去重83 题是普通去重两者之间只差一个“是否保留最后一段”。第二个变种是未排序链表。旧思路无法直接套用因为相等的节点可能分散在链表各处不再相邻。这时哈希集合方案才真正发挥价值先遍历一遍所有节点统计每个值出现的次数第二遍遍历删除出现次数大于1的节点。时间仍然是 O(n)但空间升到 O(n)。排序链表的相邻比较方案省空间未排序链表的哈希方案省时间二者本质是空间和场景的取舍。第三个变种是循环单链表。如果链表是循环的即尾节点指向头节点或 dummy那么遍历的终止条件就不再是cur.next NULL而是cur.next dummy或cur.next head。这个变种提醒我们一个核心方法论写链表遍历时第一步永远是明确“链表到底在哪里结束”终止条件搞清楚了剩下的逻辑都是套模板。第四个变种是“删除链表倒数第N个节点”它同样需要 dummy 节点但指针移动策略完全不同用到了快慢指针。把82题和这道题放在一起刷你对 dummy 节点在不同场景下的运用会有更立体的理解82题里 dummy 是为了处理“头节点可能被删”倒数第N题里 dummy 是为了统一“删除第一个节点”的边界。如果你准备面试还值得思考一个问题如果不允许新建 dummy 节点而要求必须返回原链表的头节点这个题还能不能写成一边遍历一边删除的形式答案是能但代码分支会变得非常复杂还要额外维护头节点被删后的情况。用 dummy 不是不可替代而是性价比最高的方案。面试官想看的是你的代码可读性和正确性而不是故作高深地拒绝辅助结构。在工程里可维护性永远排在“炫技”前面。最后再说一个我自己的刷题体会。链表类型题拿到题目先别急着敲代码拿笔在纸上画一条长一点的链表把 cur、dummy、重复区间的位置都标出来手动走一遍全过程再动手写。82题这类题的所有坑几乎都集中在指针更新次序和边界条件覆盖纸上模拟熟练之后代码的正确率会非常高。我自己最初也被“删完重复段后 cur 动不动”这个问题卡了很久画了三遍图才真正想明白“原地不动”才是正确解。这种图形化推演的能力刷多了以后会变成一种直觉以后遇到再复杂的链表操作心里也有底。希望这篇记录对你的刷题之路有帮助。