LeetCode 82这道题我至少见过它在三次不同公司的面试题单里出现过考察的不是什么奇技淫巧而是链表操作里最基础也最容易翻车的几个点哑节点、指针移动顺序、边界条件。题目标签虽然是“中等”但它的代码量其实很小难就难在你能不能把“删除所有重复元素”这件事想清楚——注意是所有重复一个不留。这篇就把它彻底拆开从题目解读、思路选型、代码实现到调试踩坑完整过一遍希望能帮到正在刷链表系列的朋友。1. 题目拆解先懂链表再谈去重1.1 输入输出到底长什么样题目本身很短给定一个已排序的链表的头节点 head删除原始链表中所有重复数字的节点只留下不同的数字返回已排序的链表。几个关键信息值得先划出来链表是“已排序”的这意味着重复元素一定会相邻出现不需要借助哈希表去记录出现次数这是整个算法能保持O(1)空间的前提。“删除所有重复数字的节点”不是保留一个。比如 [1, 1, 2]输出不是 [1, 2]而是 [2]。这一点和 LeetCode 83“删除排序链表中的重复元素”保留一个有本质区别。返回值是链表头节点但原始头节点也可能被删掉。比如 [1, 1, 2, 3]输入 head 指向的是第一个 1处理完之后正确答案是 [2, 3]原来的 head 已经不存在了这时候函数应该返回新的头节点。举个具体例子感受一下输入1 - 2 - 3 - 3 - 4 - 4 - 5 输出1 - 2 - 5 输入1 - 1 - 1 - 2 - 3 输出2 - 3 输入1 - 1 - 2 - 2 输出空链表1.2 它和“保留一个”的题目差异在哪LeetCode 83的经典解法很简单用一个 cur 指针从头开始如果 cur.val cur.next.val就把 cur.next 指向 cur.next.next否则移动 cur。整个过程只需要一个指针因为即使删掉了重复节点cur 本身还在它代表的就是“被保留的那个元素”。LeetCode 82难点就在于重复元素一个都不能留。这意味着你在扫描链表时不仅要找出哪一段是重复的还需要把这段整体从链表中摘除。而摘除一段链表必须知道这段的前一个节点是谁。如果是头节点开始就重复还要考虑怎么处理头部。从这就能引出两个关键设计需要一个「前驱指针」来记录重复段之前的那个节点真正执行删除操作的是它。需要一个「哑节点」来处理“头节点就被删”的边界情况让代码逻辑统一。理解这个差异基本上就理解了整道题的骨架。后面所有的写法都是在围绕“如何安全地把一整段重复节点摘掉”做文章。2. 方案选型为什么首选哑节点 双指针2.1 链表题的头疼点头节点容易被删先说说哑节点。很多链表删除类的问题最烦人的就是头节点可能被删。如果不用哑节点你得专门写一个 if 分支判断如果 head 本身要被删怎么办然后手动更新 head 指针。这种分支写多了代码又丑又容易漏。哑节点dummy的思路是在真正的头节点前面再单独 new 一个节点它不参与实际业务只是为了让你无论怎么删都能通过 dummy.next 拿到最终的头节点。dummy ListNode(0, head) prev dummy这样即使原始 head 被删了dummy.next 始终指向正确的链表头。最后 return dummy.next 就行。2.2 双指针工作的核心逻辑这里的双指针指 prev 和 curr分别承担两种职责prev指向“当前确认安全”的最后一个节点它负责在找到重复段后执行摘除操作。curr负责向前探索扫描链表判断当前节点及其后续节点是否有重复。整个循环可以概括成一句话只要发现 curr 和 curr.next 的值相等就把 curr 一路挪到重复段的最后一个节点然后让 prev 跳过整段如果 curr 和 curr.next 的值不相等说明当前节点是安全的prev 和 curr 一起往前走。需要特别注意的是在跳过重复段之后prev 不能贸然前移。因为 prev.next 刚刚被指向了重复段之后的那个节点这个新节点是否安全还需要下一次循环去判断。只有当下一次循环确认它不重复时prev 才会真正移动到它身上。这个“prev 先不急着动等确认下一个节点没问题再动”的节奏是整道题最容易想拧的地方。2.3 复杂度与空间考量时间复杂度是 O(n)其中 n 是链表长度。每个节点最多被 curr 指针走过两次一次是在外层循环中作为“探索节点”被经过一次是在跳过重复段时被快速掠过。所以整体还是线性扫描。空间复杂度是 O(1)只额外使用了 dummy 节点和两个指针变量没有用到哈希表或数组。这也是这道题相对优雅的地方虽然问题“删除所有重复值”听起来像统计类问题但因为输入已经有序完全不需要额外空间。相比“排序链表去重但不保留重复”这种衍生问题如果用先遍历一遍收集频次再遍历一遍删除的方式空间复杂度会变成 O(n)当然那样也能做出来但不是最优解。面试时候如果能有意识地给出 O(1) 空间的方案印象分会明显不一样。3. 手写实现代码逐行拆解3.1 先给 Python 版本先定义链表节点方便本地调试时自己构造输入class ListNode: def __init__(self, val0, nextNone): self.val val self.next next核心解法如下class Solution: def deleteDuplicates(self, head: ListNode) - ListNode: dummy ListNode(0, head) prev dummy curr head while curr: # 找到重复段的最后一个节点 while curr.next and curr.val curr.next.val: curr curr.next if prev.next curr: # 说明 curr 没有重复prev 向前移动 prev prev.next else: # 说明 curr 所在的这一段整体重复直接跳过 prev.next curr.next curr curr.next return dummy.next核心逻辑就是那个 if 判断prev.next curr。这个条件非常巧妙。当prev.next curr时说明从 prev 的下一个节点到 curr 之间没有经历任何跳跃也就是说 curr 不是一个重复节点它是安全的所以 prev 可以放心移到 curr 这个位置。如果prev.next ! curr说明内层 while 至少移动过 curr中间存在重复节点这时 prev.next 还是指向重复段开头而 curr 已经停在重复段末尾所以把prev.next指向curr.next就相当于把中间一整段都删掉了。举个具体的例子来模拟1 - 2 - 3 - 3 - 4初始prev dummy, curr 1。第一轮curr11 和 2 不等内层 while 不进。prev.nextdummy.next还是 head 也就是 1和 curr 相等所以 prev 移到 1 的位置curr 移到 2。第二轮curr22 和 3 不等prev.next 是 1curr 是 2不等。等等这里prev.next curr吗prev 现在指向 1prev.next 指向 2curr 也指向 2所以相等prev 前移到 2curr 移到 3。第三轮curr33 和 3 相等内层 while 让 curr 一路走到第二个 3。此时 prev.next 是 3curr 也是 3它们相等注意prev 在上一轮已经指向 2prev.next 指向第一个 3curr 经过内层 while 移动到第二个 3此时prev.next ! curr所以进入 elseprev.next curr.next也就是把 2 接到 4 上中间两个 3 被删除。prev 不动curr 移到 4。第四轮curr4prev.next 是 4curr 是 4相等prev 前移到 4curr 变 null。循环结束返回 dummy.next即 1 - 2 - 4。走一遍下来prev.next curr的语义就非常清楚了。它本质上是在问“这段路是畅通无阻走过来的还是跳过了一段重复节点如果畅通当前位置安全如果跳过当前位置是重复段的尾巴需要被摘除。”3.2 再用 Java 写一版class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode dummy new ListNode(0, head); ListNode prev dummy; ListNode curr head; while (curr ! null) { while (curr.next ! null curr.val curr.next.val) { curr curr.next; } if (prev.next curr) { prev prev.next; } else { prev.next curr.next; } curr curr.next; } return dummy.next; } }很多人问 Java 和 Python 写法一样吗其实核心逻辑完全一致区别只在于节点空值判断。Java 里必须显式写curr ! nullPython 直接while curr就行因为空对象自动判为 False。刷题时如果来回切换语言最容易犯的错就是忘记 Java 中判空条件导致NullPointerException。3.3 关键边界条件梳理写这道题只要把以下五个边界情况想清楚代码基本不会出问题。第一空链表。head 为 null直接返回 null。上面的代码里while curr根本不会进入直接返回dummy.next也就是 null天然正确。第二只有一个节点。不管这个节点值有没有重复单个节点没有重复的概念循环中curr.next为 null内层 while 不进prev.next curr成立prev 前进最后返回这个唯一节点。第三全部是重复节点比如1 - 1 - 1。内层 while 把 curr 从第一个 1 移到最后一个 1prev.next ! curr于是prev.next curr.next此时 prev 是 dummydummy.next 指向 null返回 null。这个情况正是哑节点发挥价值的地方如果没有哑节点你会发现返回的是 null但 head 指针还指向第一个 1很容易搞出悬空链表。第四重复段在中间。处理逻辑和前面模拟的一样关键是 prev 不能动要等确认下一个节点安全后再动。第五重复段在末尾。比如1 - 2 - 2curr 走到最后一个 2 时内层 while 退出prev.next ! curr直接把 prev.next 指向 null链表结束时最后一个节点被安全摘除。边界梳理清楚后你会发现其实没有任何一个 case 是真正“特殊”的哑节点把所有特例都统一掉了。4. 常见问题与排查技巧实录4.1 死循环到底是怎么产生的这道题最经典的翻车现场是死循环。不少人第一次写的时候会用类似下面的逻辑找到重复段后直接把prev.next curr.next然后让prev前移一位结果发现链表根本没变或者程序直接超时。问题通常出在对 curr 的移动节奏没有控制好。如果在摘除重复段之后你没有把 curr 指向重复段后方的第一个新节点而是让 curr 停在原处那下一轮循环可能还会扫描到同一个值导致重复处理同一个节点死循环。上面的标准代码里curr curr.next放在每个循环末尾保证无论当前节点是否重复下一轮都会从下一个候选节点开始探索。这个习惯在链表题里特别重要每轮循环结束时要确保主指针向前移动了一步。4.2 指针移动顺序为什么不能乱很多人会把prev.next curr这个判断简化成curr.val ! prev.val之类的条件当然在特定场景下逻辑可能等价但一旦涉及多个指针联动维护起来很容易出错。另一个容易迷惑的点是为什么跳过重复段后 prev 不移动来看具体例子1 - 2 - 3 - 3 - 4处理完 3 这段重复后链表变成1 - 2 - 4此时 prev 还指向 2prev.next 指向 4。如果你此时让 prev 也移动到 curr 的位置那 prev 就指向了原来的第二个 3这个节点已经被删除了后续操作会直接导致链表结构错乱。正确的节奏是curr 先去摸清前方路况确认安全后prev 才跟上。prev 永远指向“已经确认不会重复”的最后一个节点。这个思想类似走路时“探路的人”和“押队的人”的分工探路的发现问题就停下来押队的负责绕道。4.3 边界测试用例速查表在本地调试时我习惯准备一组覆盖各种情况的用例直接打印链表结果来验证输入链表期望输出考察点[][]空链表[1][1]单节点[1, 1, 1][]全部重复头节点也被删[1, 1, 2][2]头部重复原 head 被删[1, 2, 2, 3][1, 3]中间重复[1, 2, 2][1]末尾重复[1, 2, 3, 3, 4, 4, 5][1, 2, 5]多段重复[1, 1, 2, 2, 3, 3][]全部成对重复还有一个容易被忽略的点如果链表的值本身存在负数dummy 的初始值选什么标准写法ListNode(0, head)是可以的因为 dummy 节点不参与比较它的值只有占位作用你不用太担心它和链表真实值撞上。只要别把它写进循环比较逻辑里去就行。本地调试时建议写一个辅助打印函数def print_list(head): res [] while head: res.append(head.val) head head.next print(res)配合列表构造器可以快速验证自己的实现def build_list(arr): dummy ListNode(0) cur dummy for val in arr: cur.next ListNode(val) cur cur.next return dummy.next实测下来绝大多数提交报错都是因为少测试了“头节点重复”和“全部重复”这两类用例建议优先跑这两组。5. 延伸与变体一道题吃透一类链表题5.1 和 LeetCode 83 的对比LeetCode 83 的处理方式和 82 看起来很接近但有一个关键差异83 遇到重复时会保留当前节点只跳过后续的重复节点。代码可以写成这样class Solution: def deleteDuplicates(self, 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注意它没有用哑节点因为保留一个重复节点时头节点永远不会被删除所以不需要处理“删除头节点”的边界。把 83 和 82 放在一起对比学习非常划算。理解了 83 为什么不需要哑节点也就自然理解了 82 为什么必须要。很多时候面试官不是看你写不写得出来而是看你有没有“想清楚为什么要这么写”这两个题一对比思路就非常清晰了。5.2 递归解法分析除了双指针迭代也可以用递归来写。递归的核心思路是空链表返回空当前节点和下一个节点值不相等时保留当前节点继续递归处理后面的部分当前节点和下一个节点值相等时跳过所有相同值的节点然后递归处理跳过后的第一个节点。class Solution: def deleteDuplicates(self, head: ListNode) - ListNode: if not head: return head if head.next and head.val head.next.val: while head.next and head.val head.next.val: head head.next return self.deleteDuplicates(head.next) else: head.next self.deleteDuplicates(head.next) return head递归写法更接近“定义式”重复段整体丢弃不重复则保留当前值并衔接后续结果。代码很简洁但递归栈深度在极端情况下会达到 O(n)对超长链表可能触发递归深度限制。刷题阶段理解递归可行面试时我更推荐先用迭代解法因为它更稳定也更容易向面试官讲清楚空间复杂度。5.3 变体与面试扩展这道题常见变体有几种第一种把“链表”换成“数组”。如果是一个有序数组要求删除所有重复元素可以借鉴双指针的思想原地修改数组快指针扫描、慢指针记录安全位置最后截断数组长度。思路和链表版本非常相似核心都是寻找重复段的边界。第二种链表是无序的但要删除所有重复元素。这种情况下“相邻”这个条件不存在了只能借助哈希表记录每个值出现的次数先遍历一遍统计再遍历一遍删除。空间复杂度变成 O(n)但这是因为问题本身的性质变了无序情况下你必须记住每个值之前是否出现过。第三种题目改成“删除重复元素但每个重复值最多保留两个”。这种在面试里也很常见核心还是在 prev 指针的移动节奏上做文章需要额外记录“这个值已经出现了几次”代码逻辑会稍微复杂一点但套路仍然是哑节点 双指针。刷这类题我个人的习惯是不要去背模板而是把“prev 和 curr 的分工”刻在脑子里prev 永远指向安全链表的尾部curr 永远负责探索前方节点。只要这个分工明确无论是原始题还是变体都能在大方向上保持稳定。最后分享一个当初自己踩过的坑第一次提交时把prev.next curr写成了prev curr结果遇到[1, 2, 2, 3]这种中间重复的 case 时删除逻辑完全不生效白白浪费了一次提交机会。后来我在本地把每个 case 都手动追踪一遍指针状态后才对prev.next这个比较条件有了直觉。建议你也试试在纸上画一画指针的走向比自己盯着代码盲目调试要快得多。