LeetCode 82 删除排序链表重复元素：全删与留一个的边界与指针艺术

我前前后后刷过三遍 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.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前进到cur，cur再往前走一步，继续扫描。注意，在这个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 = 1，head.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 = 1，head.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 自测用例清单，提交前先跑一遍

很多人刷题直接提交，错一两个用例再回来改，既浪费时间又容易陷入慌乱。我一般会准备一个验证清单，覆盖链表删除题里最高频的边界位置：

这里尤其要覆盖“头部重复”“尾部重复”“全部重复”和“连续三段重复”。很多边界错误都发生在这些位置。写完代码后，先在纸上或调试器里对着其中一个用例完整走一遍指针，确认每个分支都走到了，再去提交。链表题的错误至少有一半来自边界分支没有走全，提前测试是性价比最高的手段。

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 的调试版，把指针每一步的落点都看明白，这个时间花得绝对值。后面你再遇到链表删除类问题，会发现大部分都能套进这一章提到的框架，速度和准确率都会明显不一样。