我前前后后刷过三遍 LeetCode 82。第一遍我拿 83 题的思路改提交后红了一片第二遍看明白了题解里那个 dummy 节点但自己动手写边界一多照样挂第三遍我才真正把“删掉所有重复值的节点”和“每个重复值保留一个”之间的那道坎迈过去。LeetCode 82 的题名全称叫“删除排序链表中的重复元素”但它的真实要求比标题看起来更严格只要某个值在链表里出现过重复那这个值对应的所有节点都得从结果中消失。比如输入[1,2,3,3,4,4,5]最终输出是[1,2,5]3 和 4 都因为“出现过重复”而全体出局而不是各留一个。这篇我打算换个讲法不贴一段能过的代码让你背而是把这道题真正考你的东西拆开——82 和 83 的差异、为什么链表题不能用数组思维硬套、哨兵节点解决什么问题、指针什么时候该动什么时候不该动、递归写法和迭代写法的取舍以及写完以后怎么用测试用例给自己兜底。把这些都搞明白你会发现这不是一道孤立的中等题它几乎覆盖了链表删除类问题的所有高频考点。1. 题目到底要干什么82 和 83 一字之差结果天差地别1.1 先看题目的精确描述与两个示例题目描述很简短给定一个已排序的链表头节点head删除原始链表中所有重复数字的节点只留下不同的数字返回已排序的链表。官方示例有两个都是理解题意的关键输入head [1,2,3,3,4,4,5]输出[1,2,5]。输入head [1,1,1,2,3]输出[2,3]。第二个示例特别值得注意链表里有连续三个 1很多人第一反应是“去掉多余的两个留一个 1”于是写出 83 题的逻辑。但 82 题要求的是这三个 1 一个都不留全部删除最终结果里只剩下 2 和 3。还有一个容易被忽略的前提链表是“已排序”的而且是升序。这意味着值相同的节点一定紧紧挨在一起不会出现“1 在开头、另一个 1 跑到链表尾巴”的情况。这个前提不是废话它直接决定了我们能不能用“局部扫描”的方式判断重复后面我会专门展开讲。很多人在读题时容易略过一个词“所有”。删除所有重复数字的节点意味着重复值没有任何幸存者。这一句话直接决定了接下来的处理模型和 83 题完全不同。我刷第一遍错就错在把“所有”理解成了“多余”最后写出来的代码实际上是 83 题的行为结果自然不对。1.2 “全删”和“留一个”的处理模型完全不是一回事83 题删除排序链表中的重复元素但保留一个要做的事是遇到相邻相同值把中间的重复节点摘掉让第一个出现的值继续留在结果里。它的本质是压缩把一段连续的[1,1,1]压缩成[1]。你只需要在扫描时发现“后一个值和当前值相同”就把后一个节点跳过当前节点保留。82 题要做的是整段摘除当发现相邻两个节点值相同我们需要定量找出这一段到底有几个节点然后把整个区间从主链中剪掉让区间前的节点直接指向区间后的第一个节点。更关键的是如果这个区间出现在链表头部头节点本身也必须被换掉。这里有个直观的对比。拿[1,1,1,2,3]来说83 题的输出是[1,2,3]82 题的输出是[2,3]。对于[1,1,2,2]83 题会输出[1,2]而 82 题直接输出空链表。我用表格把这两题的差异摆在一起大家感受一下输入83题输出保留一个82题输出全部删除[1,2,3,3,4,4,5][1,2,3,4,5][1,2,5][1,1,1,2,3][1,2,3][2,3][1,1,2,2][1,2][][1,1,1][1][]这两个操作听起来名字差不多但实际处理模型差了一个量级。83 题考的是“怎么跳过多余节点”82 题考的是“怎么识别并把一整段重复区间摘下来”这恰恰是它被归为中等难度的重要原因。1.3 为什么这题被划到中等难度很多人觉得链表题不都是送分题吗其实这道题很典型地踩中了链表操作的三个易错点。第一需要区分“重复区间”和“非重复节点”两种情况的指针走法完全不一样。非重复时当前节点保留指针正常前进重复时当前节点及同值的一批节点都不能留指针要跨过很长一段距离。如果你不把这两种情况分开处理就会写出看似正确但边界处错误百出的代码。第二头节点有可能被删除。比如[1,1,2]删除后新头变成 2你的函数返回值就不能再是最初传入的head了。头节点这个位置天然特殊没有哨兵方案的话必须单独写逻辑去处理而单独写逻辑又很容易漏。第三重复区间的长度是未知的。它可能只有 1 个重复节点也可能有 100 个。如果你在代码里只用if判断相邻两个节点值是否相等就只能删掉一个剩下的重复节点继续残留。必须用while循环把整段相同值的节点全部越过。这些问题单个拿出来都不算难但是组合在一起就很容易让思路混乱。它考察的正是对“链表引用和指针操作”的实际手感而不是背模板能解决的。2. 别带着“数组思维”做链表题指针分工决定成败2.1 数组去重和链表去重的本质区别做过数组类题目的读者一定写过双指针去重让一个慢指针指向“已保留区”的末尾一个快指针遍历整个数组发现新值时把值复制到慢指针的下一个位置最后截断。这个模型非常经典但它天然建立在两个前提上数组可以通过索引随机读写而且删除元素只需要覆盖值。链表完全不一样。它没有索引你要访问任意节点只能从头节点沿着next一个一个走过去你也没办法“覆盖”一个节点的值让它就地消失真正删除一个节点的方法是修改它前驱节点的next指针让前驱直接指向更后面的节点。这意味着数组双指针里的“写入位置”这个抽象概念在链表里必须转化为“锚点指针”的概念。一个指针永远指向结果链表的最后一个已被确认保留的节点另一个指针不断往未知区域探索。如果沿用数组思维很容易写出“只移动cur到目标位置就结束”这种代码因为链表删除永远需要知道“被删区间的前一个节点是谁”。2.2 链表删除中的指针角色锚点、探针、临时工我把这道题需要用的指针分成三类方便理解。第一类是锚点指针代码里通常叫prev它指向当前结果链表的最后一段也就是已经确认不会变的部分的末端。第二类是探针指针cur它负责扫描链表发现问题区间。第三类是临时工角色用一个变量dup_val记录重复值或者用临时指针暂存后继节点。从设计上看锚点指针不能轻易移动。当cur发现一段重复时prev必须站在原地不动等cur跳过整个重复区间后再执行prev.next cur把区间前的节点直接连到区间后的第一个节点。只有在cur没有发现重复、确认当前节点可以保留时prev才安全地前进一步prev cur。这个分工听起来简单但很多人一开始会把两个指针一起移动结果把“安全区”也推进了待删除区间链表瞬间就断成了两截。记住一个口诀重复分支里只有cur走prev原地等非重复分支里prev和cur才一起前进。2.3 排序链表带来的关键简化重复值必定相邻题目前提“已排序”是巨大的简化。升序链表意味着值相同的节点不可能被其他节点隔开它们一定紧挨着。所以我们根本不用统计每个值在全链表出现了多少次只需要在扫描的时候发现“相邻两个节点值相等”就可以直接以这个值为基准把这一整段都处理掉。换句话说判断“有没有重复”在排序链表上是一个局部行为连全局哈希表都不用。如果链表是无序的解法就完全变了先遍历一遍用哈希表统计每个值的出现次数再遍历第二遍删除出现次数大于 1 的节点。那样的解法时间和空间都会上涨。所以拿到“排序链表”四个字第一反应应该是相同值靠在一起局部扫描足够了。这个前提如果丢掉很多思路都会走偏。我把这一点放在靠前的位置讲就是希望你在写代码前先意识到这道题之所以能用指针一遍扫完不是因为删除逻辑简单而是因为排序这个条件给了我们最舒服的输入形态。3. 哨兵节点加探测循环迭代解法的设计与推演3.1 为什么必须引入哨兵节点 dummy假设不引入哨兵节点直接拿head从头开始操作你会立刻遇到一个头疼的问题如果头节点就是重复值怎么办拿[1,1,2]举例两个 1 都要删掉新的头节点是 2而你的函数手里只有旧的head它的值还是 1。你要么单独写一个while循环把head往后挪要么在函数末尾判断“新的头到底是谁”但这类特判写多了非常容易出 bug。解法里几乎都会出现一个哨兵节点创建一个dummy ListNode(0, head)这个节点的值随便起一个不会跟业务数据冲突的数它的next指向原始链表头。然后让prev从dummy出发而不是从head出发。循环结束后不管链表被怎么删除新的链表头一定还是dummy.next。这样一来头节点被删除这个问题就从“返回值特判”变成了常规指针操作。想要头节点就取dummy.next根本不需要关心它最初是不是head。这个方法在链表题里非常常用凡是“头节点可能被修改”的题目先加一个dummy基本没错。3.2 循环里每一步到底在做什么迭代版的核心循环不长但每一行都有讲究。先看伪代码骨架dummy.next head prev dummy cur head while cur is not None: if cur.next is not None and cur.next.val cur.val: dup_val cur.val while cur is not None and cur.val dup_val: cur cur.next prev.next cur else: prev cur cur cur.next return dummy.next拆开讲一下。进入循环时cur是当前扫描到但还没定性的节点。我们首先看cur和cur.next的值是否相等。如果相等说明从cur开始是一段重复区间至于有多长现在还不知道。所以先用dup_val把当前值存下来然后让cur一路往前走走到值不等于dup_val的第一个节点为止。这一步必须用while而不是if因为重复个数是未知的可能有 2 个、3 个甚至更多。跳出内层while后cur已经站在区间外的第一个节点上此时执行prev.next cur等于把整段重复节点一次性从主链上摘除。如果cur.next存在但值不相等说明cur是唯一节点是安全的。于是prev前进到curcur再往前走一步继续扫描。注意在这个else分支里prev和cur都前进而在重复分支里只有cur前进prev原地等待。这正是这道题的核心锚点不能跟着探针进入待删除区域。3.3 一版带注释的 Python 完整实现下面这版可以直接复制运行注释标了每一行的作用class Solution: def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0, head) # 哨兵节点解决头节点可能被删除的问题 prev dummy # prev 始终指向结果链表的最后一个安全节点 cur head while cur: if cur.next and cur.next.val cur.val: dup_val cur.val # 记录当前重复值作为内层循环的比较基准 while cur and cur.val dup_val: cur cur.next # 跳过整段重复节点 prev.next cur # 把区间前的节点直接接到区间后的第一个节点 else: prev cur # 当前节点无重复收编进结果链表 cur cur.next return dummy.next代码里最容易忽略的位置是dup_val cur.val这一行。如果不存这个副本直接用cur.val去跟后面的节点比一旦内层while把cur往后移动了比较基准就变了整个循环会乱套。先把基准值保存下来后面无论cur怎么动都不会影响判断。如果用 C 刷题还要额外考虑内存释放。大部分刷题平台只判断逻辑不要求释放被挑出来的节点但本地完整实现时最好把那些重复节点逐个delete。操作方式是每步先保存旧节点指针cur cur-next之后再把旧节点delete掉。最后返回ans dummy-next后记得delete dummy。这部分属于工程细节面试时可以主动提一嘴能加分。3.4 复杂度时间 O(n)空间 O(1)迭代版每个节点最多被访问两次。一次是cur正常前进时经过它另一次是它作为重复节点被内层while扫过。所以总时间是 O(n)没有多余循环。额外空间只有几个指针变量不随链表长度变化是 O(1)。这个复杂度是链表删除类题目里最理想的结果。面试时如果被问到能不能优化你可以说时间复杂度不可能低于 O(n)因为至少需要判断每个节点是否为重复值但空间上我们已经做到最少迭代只需要常数级额外空间。4. 指针移动时机才是真正的考点三种典型翻车现场4.1 翻车现场一只用 if 跳过了一个重复节点我见过很多初学者写出这样的核心逻辑if cur.val cur.next.val: prev.next cur.next表面上看发现相邻值相等后让prev直接指向cur.next好像跳过了当前节点。但如果链表是[1,2,3,3,3,4]第一次操作后变成[1,2,3,3,4]后面还有两个 3 没有被删除。你用if只是跳过了“第一个 3”剩下的 3 继续留在链表里。正确做法必须用while把整段值相同的节点跳完。在跳过之前先把重复值保存好然后让cur一直往后走直到遇到值不同的节点最后再修改prev.next。你一旦意识到“重复区间的长度是未知量”就会明白if只是权宜之计不能作为最终解法。4.2 翻车现场二重复分支里让 prev 跟着 cur 一起动这个错误比上一个更隐蔽。有人会在进入重复分支后顺手写prev cur或者在跳完重复区间后补一句prev cur理由是自己觉得“每一步都要让prev追着cur走链表才连贯”。问题在于当cur正处在重复区间时它经过的那些节点都是要被删除的。如果prev也跟着进去它就会指向一个悬空的、已经被主链抛弃的节点。随后执行prev.next 新节点时相当于让一个“已经不在主链里”的节点去接新后继结果就是主链在重复区间前的位置失去了连接链表断掉或者出现错误链接。可以这样理解prev是安全区和未知区之间的一道门。重复区间是从未知区里挖掉的部分门本身不能搬进挖掉的坑里。只有确认当前节点不重复、可以保留时才需要把门往前挪到当前节点。这道题的边界感一大半就来自这里。4.3 翻车现场三结尾出现连续重复时没有妥善置空看输入[1,2,3,3]。当cur到达第一个 3 时发现cur.next.val cur.val于是进入重复分支内层while会把两个 3 都跳过最后cur变成null。这时候必须执行prev.next cur也就是prev.next null让链表在 2 后面正常结束。但很多人这时候会漏掉接链操作或者误以为cur在 while 结束时会停在边界节点而不是null于是链表尾巴还挂着旧节点输出的结果成了[1,2,3]还是错的。类似的情况还有“从开头重复到结尾”比如[1,1,1]。内层while一路把cur推到null最后prev.next也被置为null返回的dummy.next是空链表这是正确答案。这种用例不在测试清单里跑一遍很难发现自己是否漏了收尾步骤。4.4 一个实用调试技巧每轮循环打印链表形状我刚开始学这道题时总觉得自己的逻辑没问题一提交就各种边界错后来学会在循环里打印链表了。写一个小小print_list函数每轮循环输出cur和prev指向的值再打印整条链表当前的样子问题往往一眼就看出来。下面这段带调试输出的 Python 示例可以直接本地跑def debug_print(dummy): vals [] p dummy.next while p: vals.append(str(p.val)) p p.next print(dummy - - .join(vals) if vals else dummy - None) def deleteDuplicates_debug(head): dummy ListNode(0, head) prev, cur dummy, head while cur: if cur.next and cur.next.val cur.val: dup_val cur.val print(f发现重复值 {dup_val}) while cur and cur.val dup_val: cur cur.next prev.next cur debug_print(dummy) else: prev cur cur cur.next debug_print(dummy) return dummy.next拿[1,2,3,3,4,4,5]来跑你会看到第一次发现 3 时链表输出变成dummy - 1 - 2 - 4 - 4 - 5第二次发现 4 时输出变成dummy - 1 - 2 - 5。整个过程里prev有没有被动过、cur有没有停在正确位置一眼就能核对清楚。这种“眼见为实”的调试方式比盯着代码干瞪眼高效得多。5. 递归写法从右往左消消乐代码短但要多留一份心5.1 基线条件与两种分支递归解法的核心思想是不一定要从左往右处理可以让每一层递归先处理后继子链表再回来决定当前节点怎么处理。基线条件很直接如果head为空或者head.next为空说明已经没有能跟它比较的节点了直接返回head。剩下分两支讨论。第一支head.val ! head.next.val当前节点至少跟直接后继不同先假设它可以保留。做法是把head.next指向递归处理后的子链表然后返回head。第二支head.val head.next.val当前节点所在的这一段是重复的。此时不能保留当前节点也不能简单地对head.next做递归因为head.next很可能还是同一个值。正确做法是沿着next一直找找到第一个值不等于head.val的节点然后跳过当前节点以及所有同值节点直接对这个分界点做递归。有人会问为什么不写成return deleteDuplicates(head.next)在某些用例下它也能通过但思路不够直观而且会让递归多做很多无意义的判断。先找到分界点再递归逻辑清楚效率也更好。5.2 完整递归代码class Solution: def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]: if not head or not head.next: return head if head.val ! head.next.val: head.next self.deleteDuplicates(head.next) return head cur head.next while cur and cur.val head.val: cur cur.next return self.deleteDuplicates(cur)这个代码非常短但每一行都有意义。非重复分支让当前节点保留并且先让后继子链表处理干净再接回来。重复分支里cur会一路滑到与head.val不同的节点或者空节点然后整段重复节点被丢弃继续递归处理后面的部分。比如[1,1,1,2,3]最外层发现 1 是重复值cur直接走到值为 2 的节点返回递归处理[2,3]的结果三个 1 全部不要。你不用担心链表会断因为递归返回值会把结果链表从后往前逐层拼接起来。5.3 递归推演连续重复和末尾重复各走一遍我用两个例子把递归的实际过程推一遍。先是[1,1,1,2,3]。最外层head.val 1head.next.val 1走重复分支。cur从head.next开始依次跳过两个 1停在 2。然后返回deleteDuplicates(2)。递归处理[2,3]时2 和 3 不相等保留 2并把2.next指向deleteDuplicates(3)的返回值 3。最终得到[2,3]。再推[1,2,3,3]。最外层head.val 1head.next.val 2走非重复分支保留 1把head.next指向deleteDuplicates([2,3,3])的结果。进入[2,3,3]后2 和 3 不等保留 2再递归[3,3]。此时 3 和 3 相等cur被推成null返回deleteDuplicates(null)也就是null于是2.next null。最终结果[1,2]。递归在这里像不像“从右往左消消乐”后面处理完了前面的节点才决定自己要不要留下。理解了这条主线你就不会把递归理解成“换一种写法遍历”而是真正把它当成“由后向前归约”的手段。5.4 空间代价递归版是 O(n)长链表慎选迭代版空间是 O(1)递归版因为系统栈要保存每层调用的现场最坏情况空间是 O(n)。在链表很长的情况下递归可能出现栈溢出。拿 Python 来说默认递归深度大概在 1000 左右如果链表节点数几千甚至上万递归版很容易直接异常。面试时我建议默认先讲迭代版再补充一句“递归版也有但空间是 O(n)生产环境我更倾向迭代”会显得你有工程意识。递归版的价值更多在于代码短、逻辑集中适合快速表达思路。如果你对递归敏感用它来验证自己对问题的理解完全可行但最终提交或交付我还是推荐迭代版。6. 写完之后的验证清单边界用例与延伸思考6.1 自测用例清单提交前先跑一遍很多人刷题直接提交错一两个用例再回来改既浪费时间又容易陷入慌乱。我一般会准备一个验证清单覆盖链表删除题里最高频的边界位置输入期望输出核心考察点[][]空链表[1][1]单节点[1,1,2][2]头部重复[1,2,2][1]尾部重复[1,1,1,2,3][2,3]头部连续多重复[1,2,2,3,3,3,4][1,4]中段多重复[1,1,1][]全部重复[1,2,3,3,4,4,5][1,2,5]题目标准示例这里尤其要覆盖“头部重复”“尾部重复”“全部重复”和“连续三段重复”。很多边界错误都发生在这些位置。写完代码后先在纸上或调试器里对着其中一个用例完整走一遍指针确认每个分支都走到了再去提交。链表题的错误至少有一半来自边界分支没有走全提前测试是性价比最高的手段。6.2 复杂度闭环与面试话术迭代版的时间复杂度 O(n)、空间复杂度 O(1)这个结论要能自己推导出来。时间为什么是 O(n) 而不是 O(2n)因为内层while扫过的每个节点只会被扫一次cur不会回头指针整体访问次数是线性的。空间为什么是 O(1)因为只用了dummy、prev、cur和dup_val这几个固定变量和链表长度无关。面试如果追问“能不能更快”你可以回答时间复杂度不可能低于 O(n)因为至少要判断每个节点是否重复每个节点都值得看一次但我们已经做到“在必须访问的前提下只用常数级额外空间”这就是这类题的理论下限。至于递归版要换成时间 O(n)、空间 O(n)这也是我推荐默认给迭代版的核心原因。6.3 从这道题沉淀出来的“链表删除框架”这道题做完之后不应该只是记住答案。它真正留下的是一个可以复用的操作框架凡是头节点可能被删的题目先加dummy哨兵凡是需要跳过长度不确定区间的题目内部用while循环并且让锚点指针留在区间外凡是比较基准会在循环中变化的扫描先把基准值保存到临时变量凡是返回新链表头的题目最后统一返回dummy.next。这几个原则能直接迁移到不少链表题上。比如 83 题你可以把“跳过整段”改成“跳过多余节点”思路立刻通19 题删除链表倒数第 N 个节点同样用哨兵解决头节点删除24 题两两交换节点、328 题奇偶链表本质上都是“锚点指针带头扫描”的模式。你会发现很多所谓难题拆开以后都是这些基础操作的组合。最后说点个人感受。这道题我真正吃透靠的是把代码丢进调试器一遍遍看打印输出而不是背题解。特别是prev和cur移动顺序这件事看十遍文字不如自己跑一遍[1,2,3,3,4,4,5]来得清楚。如果你刷这道题也卡过别急着点开下一个题解先亲手写一份带 print 的调试版把指针每一步的落点都看明白这个时间花得绝对值。后面你再遇到链表删除类问题会发现大部分都能套进这一章提到的框架速度和准确率都会明显不一样。