力扣第82题题目全称是“删除排序链表中的重复元素 II”算是我刷链表题时印象很深的一道。别看它只比另一道同名题多了一个“II”难度和考察点完全是两个层次。如果你以为它只是“把重复的删到只剩一个”那就理解错了——这道题要求的是把重复的节点整组删掉一个都不留。比如链表[1,2,3,3,4,4,5]最后要变成[1,2,5]。我在面试和平时刷题的过程中见过太多人在“删除排序链表中的重复元素”上栽跟头要么没处理头节点本身就要被删的情况要么在重复段跨越多个节点时指针绕晕要么递归解法写出来压根不满足题意。这篇文章我就把这道题的完整解法、边界条件、代码实现以及我从这道题里总结出的链表通用套路一次讲透。1. 读懂“删除所有重复”和“保留一个重复”的差别1.1 这道题和力扣83题的本质区别在哪里力扣83题“删除排序链表中的重复元素”输入[1,1,2,3,3]输出[1,2,3]。它做的是“去重”每个值只保留一个节点。而82题同样的输入输出是[2]——值1和3在链表中出现了多次连它们本身带所有副本一起全部删除。这个差别直接改变了解题的策略。83题可以用“快慢指针”一路扫过去遇到相同值就跳因为结果里始终要保留第一个出现的节点。但82题不行你没法在扫描时立刻决定“当前这个节点要不要留”因为你还不知道后面有没有和它相等的节点。我习惯用一个生活化的类比来解释83题好比签到表里有人重复签了三次你只需要保留一条记录82题呢是只要发现这个学号重复签了多次就把这个学号的所有签到记录全部作废。这样一来你要处理的就不再是“单节点要不要跳过”而是“一整段相同值的节点要怎么识别并整体摘除”。1.2 一个自测用例先帮自己建立直观在动手写任何代码之前我强烈建议先在纸上跑一遍样例。就拿力扣官方的示例二来说head [1,1,1,2,3]预期输出[2,3]这个例子最直观的点在于链表的头节点1本身就是要被删除的。很多人在写迭代解法时习惯用一个变量指向head然后从头开始比较。但一旦head就是要删的那个重复段整个链表的新头部变成了2这时候如果还是以原来的head为返回基准答案必然出错。所以拿到这道题先自己在草稿纸上把1,1,1这一段标记出来再去看2,3你会更容易理解后面的虚拟头节点方案也更容易理解为什么head不是一个可靠的返回锚点。2. 虚拟头节点为什么没有它你就会在边界疯狂出错2.1 头节点恰好是重复值时返回结果怎么变我见过太多人写出“看着差不多”的代码跑[1,2,3,3,4,4,5]能过换到[1,1,2]就直接返回了错误结果。原因几乎都指向同一个设计盲区迭代删除时如果重复段包含原链表头节点那么删除完成后的链表头是谁你拿什么变量来记住它举个例子head [1,1,2]删除所有重复后应该返回[2]。如果你在代码里用prev和cur两个指针从真正的头节点开始遍历当prev指向第一个节点1、cur指向第二个节点1时发现相等你把prev.next接给2后面的节点也就是删除了两个1。此时链表结构变成了以2开头但你的脑袋里如果没有一个“锚点变量”提前记住这个新头最自然的做法是继续返回head这个head仍然指向那个已经不属于结果链的节点那么返回值就是[1,2]大错特错。要让代码在所有情况下都自洽思路不是想尽办法去维护head而是索性在真正的头节点之前额外加一个“虚拟头节点”让所有逻辑都基于它进行。这个虚拟头节点在返回时不参与结果只是为了让删除操作有一个永远不需要特殊处理的起点。2.2 虚拟头节点的正确用法和初始化细节虚拟头节点的写法极其简单但细节上有几处需要养成肌肉记忆ListNode dummy new ListNode(0, head); ListNode cur dummy;我习惯让cur从dummy开始而不是从head开始这样做的直接好处是判断cur.next.val cur.next.next.val时我永远不会因为cur一开始落在头部而漏掉从头就开始的重复段。很多人的代码在普通场景下没问题一遇到[1,1,2]就出错正是因为cur从head出发head自身就带着重复值但代码又没有单独处理头部删除的分支。如果你的语言版本不支持在构造器里直接传next参数比如一些老版本的C环境可以这样写ListNode dummy new ListNode(0); dummy.next head; ListNode cur dummy;虚拟头节点的值随意给我用0只是因为习惯它不会被比较到。关键是dummy.next要初始化为head并且最后返回的是dummy.next而不是head。把这些一次写清楚后面所有逻辑就不用在“头节点要不要特判”这件事上反复纠结了。3. 双指针前后脚移动这道题最稳的迭代解法3.1 指针移动策略的完整推演迭代解法里我用的是“快慢双指针”思路但这里的“快慢”和链表找环那个场景不一样我更愿意叫它“侦察指针”和“确认指针”。整个流程可以拆成三步当前指针cur固定在某个位置先让侦察指针probe从cur.next出发一路向前探测直到找到第一个与cur.next.val不同的节点。如果probe移动了说明中间存在重复段直接把cur.next接到probe指向的节点。如果probe没有移动说明cur.next是唯一的让cur正常前进一步。以[1,2,3,3,4,4,5]为例最开始时cur在dummycur.next是节点1。侦察指针从1往后看节点2的值不等于1所以probe停在2说明1不重复cur移到1。接着看1.next 2往后侦察3不相等2保留cur移到2。再看3侦察指针发现3 - 3 - 4即走到了4才停下来说明3这一整段都是重复的于是把cur.next从第一个3直接接到4并删掉中间两个3。接下来4,4,5同理4被整体删除5保留。最终dummy.next就是1 - 2 - 5。3.2 代码实现与关键行注释我把完整代码贴在下面注释写的是我在面试现场手撕这份代码时脑子里反复确认的要点public ListNode deleteDuplicates(ListNode head) { // 空链表或单节点链表可以直接返回省一次无用功 if (head null || head.next null) { return head; } ListNode dummy new ListNode(0, head); ListNode cur dummy; // cur 永远指向“已确认保留的链表的最后一个节点” while (cur.next ! null cur.next.next ! null) { if (cur.next.val cur.next.next.val) { // 发现了重复段先记住这个重复值 int duplicateVal cur.next.val; // 把所有值为 duplicateVal 的节点全部跳过 while (cur.next ! null cur.next.val duplicateVal) { cur.next cur.next.next; // 直接跨过当前重复节点 } } else { // cur.next 不是重复节点cur 正常前移 cur cur.next; } } return dummy.next; }这段代码的核心点在于我判断“是否存在重复段”看的是cur.next和cur.next.next是否相等而不是拿一个固定值去到处比较。一旦相等就锁定这个值然后循环把等于这个值的节点全部摘除。这样写的好处是不管重复段是2个节点还是10个节点都能统一处理。如果换成Python逻辑完全一样def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0, head) cur dummy while cur.next and cur.next.next: if cur.next.val cur.next.next.val: val cur.next.val while cur.next and cur.next.val val: cur.next cur.next.next else: cur cur.next return dummy.next这段代码的时间复杂度是 O(n)因为每个节点最多被访问两次一次作为cur.next被检查一次作为重复段成员被跳过。空间复杂度 O(1)整个过程只靠几个指针变量没有额外的数据结构。这两个复杂度在面试时一定要能当场说清楚尤其要解释为什么不是 O(n²)——虽然有两层循环但内层循环不会重复扫描已经跨过的节点。4. 递归解法把“要不要保留当前节点”交给子问题4.1 递归的口径设计返回处理后的链头迭代解法的优点是直观可控但有些面试官会追问“你能用递归实现吗”或者你自己想进一步加深对链表结构的理解。递归解法的关键在于想清楚函数的“契约”是什么。我定义的递归函数是deleteDuplicates(head)返回一个新链表的头节点这个新链表已经删除了head起始的链表中的全部重复节点。基于这个口径我只看当前节点和它下一个节点如果head.val ! head.next.val说明当前节点值得保留我只需要让head.next等于“对后面那段链表继续做删除操作的结果”。如果head.val head.next.val说明当前节点身处一个重复段。我先一路跳过所有和head.val相等的节点然后“对跳过之后的第一个节点继续做删除操作”。人脑在理解递归时最容易犯的错是去“模拟递归树的完整展开”。我自己的经验是不要想太深只盯着“我这一层要做什么”和“子问题返回什么”两层逻辑写清楚就够了。4.2 代码实现与两种写法的对比public ListNode deleteDuplicates(ListNode head) { if (head null || head.next null) { return head; } if (head.val head.next.val) { // 当前节点和下一个节点相等说明当前节点必然要被删除 while (head.next ! null head.val head.next.val) { head head.next; } // head 现在停在重复段的最后一个节点上继续处理它之后的节点 return deleteDuplicates(head.next); } else { // 当前节点保留递归处理后面的链表 head.next deleteDuplicates(head.next); return head; } }这段代码我每次读都会觉得它优雅得过分没有虚拟头节点却依然能正确删除头部重复段。原因在于“递归天然知道新链表的头是谁”——return deleteDuplicates(head.next)这一句直接把重复段之后第一个不重复的节点作为结果传回去了。迭代和递归各有各的适用场景。我个人的看法是面试时优先写迭代因为不容易爆栈也更容易解释清楚但如果面试官明确考察递归思维这种解法不仅代码简短还能体现出你对“子问题划分”的理解。两种解法的对比如下对比维度迭代解法递归解法额外空间O(1)只用指针O(n)递归调用栈开销代码可读性逻辑显式步长清晰简洁优雅但需要契约思维对超长链表的稳健性安全链表长度过万时可能栈溢出面试讲解难度中等边写边讲节奏好较高需讲清递归口径如果你的目标只是通过力扣这道题本身两种都能过但如果你在准备面试我建议先熟练掌握迭代再拿递归作为加分项展示。5. 边界条件测试清单与易错点盘点5.1 五组必测用例我把这道题真正容易翻车的边界条件整理成一张清单。刷题时别只跑示例就跑一定要把这些用例一一过一遍用例输入预期输出考点说明空链表[][]判空是否写在最前面单节点[1][1]链长1时必须原样返回全部重复[1,1,1][]删除后链表可能为空头节点重复[1,1,2,3][2,3]虚拟头节点是否发挥作用无重复[1,2,3][1,2,3]正常遍历逻辑不误删我在代码里把head null || head.next null作为第一道防线就是为了在只涉及0个或1个节点时省去后面所有逻辑也避免访问head.next.next导致空指针。5.2 最容易踩的三个坑第一个坑是死循环。有些人在发现重复后直接把cur cur.next这样会导致重复节点的前驱关系没断开链表在某些场景下永远走不到null。正确做法是修改cur.next指针的指向而不是移动cur本体等确认当前段没有重复后再让cur前进。第二个坑是空指针。在判断cur.next.val cur.next.next.val之前必须确认cur.next不是null。很多人写的循环条件只检查了cur ! null然后在循环体内访问cur.next.val直接就崩了。我习惯把循环条件写成while (cur.next ! null cur.next.next ! null)这样每一次访问都建立在节点存在的前提上从根上避开空指针。第三个坑是返回了错误的头。迭代解法里只要用了虚拟头节点返回值必须是dummy.next但总有人写到结尾一顺手就return head。尤其是整条链表全被删除时head指向的节点早已被绕过dummy.next才是真正的null。我自己调试这类题时有一个习惯在每个关键节点前后加临时输出打印当前cur.val和cur.next.val。如果是本地环境还好但力扣的在线编辑器不太方便打日志我就在草稿纸上画一个五六个节点的链表用箭头标出每次指针变化。画几轮之后很多之前想不明白的指针关系就顺了。这道题尤其值得花时间画图因为它考验的正是对指针状态迁移的敏感度。6. 从82题延伸出去链表题的通法与面试技巧6.1 链表的“操作三件套”虚拟头 双指针 断开重接经常刷链表题的人应该能感觉到这类题目翻来覆去就是几个固定套路。把82题吃透后我建议有意识地把这些套路抽象出来因为它们会在其他题目里反复出现比如力扣的“两两交换链表中的节点”“反转链表 II”“重排链表”等。第一件套是虚拟头节点。凡是可能修改头节点的题无脑加一个dummy基本不会错它最大的价值不是性能而是让代码少很多“如果头节点也要特判”的分支。第二件套是双指针。这道题里是“确认指针 侦察指针”其他题目里可能是“快慢指针找中点”“前后指针找倒数第k个节点”。双指针的核心在于明确两个指针的职责边界82题里cur负责维护“已处理完成的链表尾部”侦察指针负责“找出重复段的边界”边界清晰了逻辑自然不乱。第三件套是断开与重接。很多链表操作本质上就是“把某些节点的next指针重新连到别处”。82题里重复段的删除本质是cur.next不断指向更远的节点直到跳过整个重复段。这个“把指针接到哪里”的判断永远比“被跳过的节点内存怎么办”重要得多。析构是语言层面的问题指针重连是算法层面的问题两者别混在一起想。6.2 面试时怎么把这道题讲得漂亮如果你在面试中遇到这道题我建议按以下顺序表达这也是我帮朋友模拟面试时反复打磨出来的框架第一步先确认题意明确“所有重复节点都要删干净一个不留”同时追问输入是否已排序——排序这个前提直接决定了能不能用顺序扫描解决。第二步讲一个最直接的思路比如“用一个Map记录每个值出现的次数第一次遍历统计频率第二次遍历把频率大于1的节点全跳过”然后把空间复杂度 O(n) 说清楚。第三步基于“链表已经排序”这个条件提出优化方案不需要统计频率只需要在遍历时比较相邻节点用虚拟头节点处理头部删除用双指针跳过重复段整体复杂度降到 O(1) 额外空间。这样由浅入深地讲面试官能顺着你的思路走也能看出你对复杂度有清晰认知。我在实际中遇到过一些候选人一上来就写最优解代码确实对但因为没讲清楚为什么要用虚拟头节点反而显得像背题。把思维过程摊开来说效果通常更好。另外还有一个很实际的小建议如果是在纸上写代码先写主流程再补边界判断不要一上来就把if (head null || head.next null)写在最前面然后忘记后面还要修改链表的指针如果是在力扣编辑器里写先把用例跑完再回头检查有没有多余的空指针风险点。千万别小看这些细枝末节我见过太多人代码逻辑明明对就因为漏了判空在面试官面前红了脸。把82题练到能闭着眼睛写出“虚拟头 值锁定 整段跳过”这个主流程你对链表操作的基本功就算真正过关了。