链表类的题目在 LeetCode 上有很多经典题但 82 题在我心里一直是个“分水岭”——能做对的人不一定真的理解链表但理解链表的人一定能把 82 题写得干净利落。它不涉及复杂的数据结构也不考什么高深的算法核心就是“如何在一个排序链表中把所有重复出现的节点全部删掉”。这个“全部删掉”和 83 题的“保留一个”完全是两种思路很多人第一次做的时候都会在指针移动上栽跟头。如果你正在准备面试或者想系统过一遍链表操作这道题值得认真拆解。它不仅帮你理清“哑节点”的妙用还能锻炼你对“指针更新时机”的敏感度。我会从题目含义、迭代写法、递归写法、复杂度、边界情况到常见调试坑一次性讲透。1. 题目理解与解题思路1.1 题目到底在问什么先看题目要求给定一个已排序的链表删除原始链表中所有重复数字的节点只留下不同数字的节点。注意这里的“只留下”不是指“每个数字保留一个”而是说重复出现的数字一个都不留。举个例子链表1 - 2 - 3 - 3 - 4 - 4 - 5因为 3 重复了4 也重复了所以这两个数字的节点全部删除最后结果应该是1 - 2 - 5。如果链表是1 - 1 - 1 - 2 - 3那么 1 出现三次一个不留结果是2 - 3。这个“全部删除”是核心区别。很多人在做的时候会下意识参照 83 题想着“跳过重复的保留一个”结果代码写完发现答案不对。所以第一步一定要把题意的差异刻在脑子里83 题处理完重复元素会留下一个82 题处理完重复元素会全部消失。另外注意“排序链表”这个前提如果链表不是排好序的那“重复元素”就不好用一次线性扫描来判断了因为相同的值可能分散在不同的位置。题目给了排序这个条件就意味着所有相同的值一定是连续出现的这是我们能用一遍遍历解决问题的基石。从数据结构上看链表删除操作的核心是“让前一个节点的 next 指向后一个节点”。但这里删除的是一个区间我们需要知道这个区间的“前驱”和“后继”然后一次性把区间内的所有节点摘除。1.2 为什么需要哑节点链表的头节点也可能被删除。比如1 - 1 - 2头节点是重复值如果直接操作头指针删除之后头节点就会变化。用裸指针操作时为了应对“头节点被删”的情况通常有两种方案先单独处理头节点找到第一个不重复的节点作为新头。在头节点前面加一个“哑节点”dummy node让所有删除操作都统一从哑节点的下一个节点开始。第二种是更通用的方式。哑节点的作用在于它把“删除头节点”这个特殊情况转化成了“删除普通节点”的常规操作。因为哑节点永远不可能被删除所以我们只需要维护好一个指向哑节点的指针最后直接返回dummy.next作为新链表头即可。这里有一个很关键的心理模型不要把哑节点当成“哨兵”或者“额外节点”来看它只是我们人为制造的一个“前驱节点”让代码在处理第一个真实节点时逻辑和处理后续节点完全一致。有了哑节点我们就不需要写一堆if head None or head.next None之类的特判代码会简洁很多。1.3 删除策略跳过整段重复值既然链表是排序的重复值一定连续出现。那么我们要做的就是“找到一段连续相同值的节点区间”然后判断这个区间的长度是否大于 1如果大于 1就把整个区间从链表中摘掉。用指针来描述就是维护一个当前节点的前驱指针prev和一个用于探测的指针cur。cur从prev.next开始往前探索只要发现cur.next的值和cur的值相同就继续往前移动直到遇到不同的值。此时cur停在这一段重复值的最后一个节点上。如果prev.next和cur是同一个节点说明这段区间只有一个节点没有重复直接让prev cur继续往下走。如果prev.next ! cur说明这一段至少有连续两个节点值相同那么prev.next cur.next就能把所有重复节点一次性跳过去。这个策略的关键在于我们不需要逐个删除节点只需要改变指针的指向。链表删除的本质就是“跳过节点”。这个思路也是面试官最希望听到的——先讲清楚策略再写代码整个逻辑会非常清晰。2. 迭代实现一次遍历解决2.1 核心逻辑与指针设计迭代写法的骨架非常固定。先创建哑节点dummy ListNode(0) dummy.next head然后维护两个指针prev指向“已经确定没有重复的最后一个节点”cur指向当前正在探测的节点。初始时prev dummycur head。循环条件是什么很多人会写while cur and cur.next。其实更稳妥的是while cur然后在循环体内根据情况推进cur。我们来看下面的逻辑while cur: # 如果 cur 和下一个节点值相同就一直往前走 if cur.next and cur.val cur.next.val: while cur.next and cur.val cur.next.val: cur cur.next # 此时 cur 指向重复段的最后一个节点 prev.next cur.next cur cur.next else: # 没有重复prev 和 cur 都往前移动 prev cur cur cur.next注意几个细节内层循环结束后cur停在重复段的最后一个节点。此时cur.next就是第一个不重复的节点也可能是 None。prev.next cur.next把整个重复段跳过了。然后cur cur.next让cur指向下一个需要探测的节点。注意在这个分支里prev不动。因为prev指向的节点已经和后面的节点断开了后续需要继续用它作为前驱来判断新的cur是否重复直到确定下一个不重复节点后prev才推进。这个“在删除分支里prev不移动”的细节非常关键。很多人的代码在删除完之后立刻执行prev prev.next结果就乱了。因为如果这一段的重复节点被删除后prev.next已经指向了新的节点你并不知道这个新节点是否还会和后面的节点重复所以不能贸然把prev推进。一定要等到“这个节点被确认是不重复的”之后才能让prev走到它头上。2.2 代码实现Python / C先贴一份完整的 Python 解法# Definition for singly-linked list. # 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 cur head while cur: if cur.next and cur.val cur.next.val: # 找到重复段的最后一个节点 while cur.next and cur.val cur.next.val: cur cur.next # 跳过整个重复段 prev.next cur.next cur cur.next else: # cur 是唯一值prev 和 cur 同时前进 prev cur cur cur.next return dummy.next再看 C 版本逻辑完全一致只是换了一套指针语法class Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode* dummy new ListNode(0, head); ListNode* prev dummy; ListNode* cur head; while (cur) { if (cur-next cur-val cur-next-val) { while (cur-next cur-val cur-next-val) { cur cur-next; } prev-next cur-next; cur cur-next; } else { prev cur; cur cur-next; } } ListNode* result dummy-next; delete dummy; return result; } };很多语言题解喜欢在prev.next cur.next之后不更新prev但要注意如果这里直接prev prev.next当链表后面还有连续重复段的时候前驱节点的信息就丢了。我们看一个例子1 - 1 - 2 - 2 - 3初始 prevdummy, cur1。发现 1 重复内层循环把 cur 移动到第二个 1。prev.next 指向第二段的第一个 2cur 指向这个 2。此时如果执行 prev prev.nextprev 就会指向 2。继续循环发现 2 也重复需要删除 2但 prev 就是待删除段的第一个节点删除时prev.next cur.next会把自己后面的节点接到自己后面而 prev 本身还在链表里结果链表变成了 1? 不对这里 prev 是第二个 2它是待删除的节点你用它做前驱删除逻辑就错了。所以必须坚持“prev 永远指向已确认不重复的节点”这一原则。在遇到重复段时prev 保持不动直到 cur 移动到某个值确实只出现一次才让 prev 前进到 cur 的位置。2.3 边界情况梳理链表题目最怕的就是边界考虑不全。82 题的边界情况其实很典型链表为空head is None直接返回 None。上面的代码里cur 为 Nonewhile 不进返回 dummy.next 即 None没问题。链表只有一个节点cur.next 为 None进入 else 分支prev 和 cur 都前进最后返回原节点正确。整个链表全部重复比如1 - 1 - 1dummy.next 最终会被置为 None返回空链表正确。重复段在末尾比如1 - 2 - 3 - 3prev 停在 2cur 移动到第二个 3prev.next cur.next 即 None正确。重复段在开头比如1 - 1 - 2prevdummycur 移动到第二个 1prev.next cur.next 指向 2返回 dummy.next 为 2正确。连续多段重复比如1 - 1 - 2 - 2 - 3上面我已经分析过只要 prev 不在删除分支推进就能依次跳过两段重复最后返回 3。不同语言处理空指针的习惯不同Python 里用NoneC 里是nullptrJava 是null。写的时候注意别混。另外dummy的初始值随便给个 0 或者 -1 都行它不会参与值比较。只要保证dummy.next head即可。有些刷题者为了省事会直接写ListNode dummy; dummy.next head;这在 C 里没问题但注意不要用ListNode* dummy new ListNode(0);之后忘记释放内存虽然刷题平台不检查内存泄漏但好习惯还是得有。3. 递归实现与思维转换3.1 递归函数的返回值定义迭代写法是链表题的主流但 82 题用递归来解也能让思维更通透。递归的关键在于明确每个递归调用返回什么。这里我们定义deleteDuplicates(head)返回的是“从head开始删除所有重复节点后的新链表头”。对于当前head我们只需要判断head是否是一段重复值的开头。怎么判断如果head.next存在且head.val head.next.val说明head是重复的。那么我们要找到这一段重复值一直延伸到哪个节点结束。假设一直延伸到node那么node.next才是第一个不重复的节点。因为head这一段全部要删掉所以直接从deleteDuplicates(node.next)开始返回即可不用管head和中间的节点。如果head.val ! head.next.val说明head本身不重复那head应该保留head.next应该指向deleteDuplicates(head.next)返回的结果。这里有一个容易绕晕的地方递归里“跳过整段重复”的操作不是靠改变指针而是靠“抛弃”这些重复节点。比如1 - 1 - 2 - 3递归调用deleteDuplicates(head)时发现1和next 1相等于是继续往下找到最后一个 1然后直接返回deleteDuplicates(2)的结果。中间那两个 1 就这么被“扔掉了”。这种思考方式更贴近“函数式”思维——不去修改链表的连接关系而是通过返回值重新构造链表的连接关系。3.2 代码实现与复杂度递归解法的代码非常简洁Pythonclass Solution: def deleteDuplicates(self, head: ListNode) - ListNode: if not head or not head.next: return head # 如果当前节点是重复段的开头 if head.val head.next.val: # 找到重复段的最后一个节点 while head.next and head.val head.next.val: head head.next # 此时的 head 是重复段最后一个节点head.next 之后是安全的 return self.deleteDuplicates(head.next) else: head.next self.deleteDuplicates(head.next) return head这个写法里while循环的作用和迭代里的内层循环一样都是定位重复段的末尾。注意while的条件是head.next and head.val head.next.val其中head.val是固定不变的因为我们已经确定当前节点和它的下一个节点值相同所以一直向后移动直到下一个节点的值不同或为空。如果进入 else 分支说明head单独出现那就把head.next交给递归处理然后把返回的结果接在head后面。每次递归调用处理一个“不相等的值段”所以有多少个不同的数字就会有多少层递归。最坏情况下链表里每个值都不一样那么递归深度就是链表长度 n。空间复杂度取决于递归栈的深度是 O(n)。而迭代写法只用 O(1) 额外空间。所以在面试中如果你提了递归版本最好补充说明空间复杂度的代价然后表示实际工程中会倾向于用迭代。递归版本还有一个隐蔽的问题如果链表很长比如上万节点递归可能导致栈溢出。LeetCode 的测试数据一般不会那么极端但在真实的分布式环境下递归处理链表基本不可取。不过理解递归能帮你训练“自上而下”的抽象能力对理解更复杂的树、图问题也有好处。4. 复杂度分析与算法优劣4.1 时间复杂度 O(n) 怎么来的不管是迭代还是递归每个节点最多被访问常数次。迭代写法里外层 while 每次要么让cur前进一步要么让内层 while 把cur移动到重复段末尾。可以发现cur指针在整个过程中只会向右移动不会回头也不会跳过某个点然后再次访问它除了在重复段内部是连续前进的。因此总访问次数不超过 2n时间复杂度为 O(n)。递归写法中每个节点也会被扫描一到两次一次是判断head和head.next是否相等另一次可能是在 while 循环中向后移动。整体仍然线性。这种“扫描一遍就能解决”的性质完全依赖于链表是排好序的。如果链表无序你需要借助哈希表统计每个值的出现次数然后再遍历一遍删除那样时间复杂度也是 O(n)但空间复杂度会变成 O(n)。这也是为什么题目特意标注“排序链表”。4.2 空间复杂度迭代 O(1) vs 递归 O(n)迭代版本只用常数个指针变量额外空间是 O(1)。递归版本每层递归都要压栈额外空间是 O(n)最坏情况。很多刷题攻略里会告诉你“递归简洁但空间复杂度高”。但这里有一个更微妙的点在 C 中迭代版本我们手动new了一个dummy节点严格来说这也算是 O(1) 的额外空间因为它和链表长度无关。但如果用new而不 delete在一些内存检查严格的场景会被扣分。在 LeetCode 上通常不判这个不过正式面试时可以提一句“我这里 new 了一个哑节点最后会释放”显得代码严谨。对于追求极致空间的人来说也可以不用哑节点单独处理头部但那样代码会多出很多分支可读性下降。拿 O(1) 的常数空间换代码简洁性完全值得。4.3 与 83 题对比加深理解LeetCode 83 题是“删除排序链表中的重复元素”保留一个。它的代码通常是cur head while cur and cur.next: if cur.val cur.next.val: cur.next cur.next.next else: cur cur.next return head这个写法里cur始终指向“已确认保留的节点”遇到重复就直接让cur.next跳过重复节点。它不需要哑节点因为头节点永远不会被删除——就算前面有重复头节点也会被保留。而 82 题是“全部删除”所以头节点可能被删。这导致我们需要一个 prev 来记录前驱并且 prev 不能像 83 题的 cur 那样随意前进。我在面试中经常用这两道题做“组合拳”先让候选人写 83再改写成 82。很多人 83 写的很顺手但 82 会卡在 prev 的更新时机上。我后来发现一个特别好的类比83 题像排队时“遇到和前面人一样的人就把它踢出去”而 82 题像“发现连续几个人都穿着一模一样的衣服就把这整个群体一起清走”。清走群体之后你不能再往前走因为下一个群体可能也穿得一样你只能站在原地继续观察。这个类比虽然有点生活化但对初学者很有帮助。理解了“删除重复段之后不要急着移动 prev”这个点82 题就基本拿下了。5. 常见错误与调试心得5.1 忘了处理末尾连续重复最经典的错误是只考虑中间重复没有考虑链表末尾就是重复段。比如链表1 - 2 - 3 - 3内层 while 会把 cur 移动到最后一个 3然后prev.next cur.next即prev.next None这一步是必须的。但有些人写内层循环时条件写成了while cur.next and cur.next.val cur.val这个没问题。怕的是外层循环条件写成while cur and cur.next当 cur 走到最后一个 3 时cur.next为 None循环退出最后一个 3 和前面的 3 没有被处理。也就是说如果遍历条件漏掉了最后一个节点的情况就会导致末尾重复节点没被删干净。我的习惯是外层循环用while cur把“末节点处理”交给内层循环和分支逻辑而不是依靠外层条件。这样思考更统一只要 cur 存在就检验它是不是某个重复段的一部分。5.2 哑节点误用、返回错节点另一类高频错误是返回head而不是dummy.next。如果头节点被删了head仍然指着旧的头节点这时返回head就错了。记住一旦用了哑节点最后一定要返回dummy.next。还有一类错误是给哑节点赋了一个和链表值冲突的值然后拿它参与比较。实际上哑节点的值永远不会用来和链表节点比较因为我们的比较只在cur和cur.next之间进行prev永远不参与值判断。所以哑节点的初始值随便写但为了语义清晰我通常写 0 或 -1。5.3 指针移动逻辑混乱在迭代版本里容易出错的是两个分支中prev和cur的更新责任。我总结了一个“口诀”有重复prev不动cur走到重复段末尾后通过prev.next接上cur.next然后cur继续后移。没重复prev和cur一起后移。这个口诀我在每次写代码前都会默念一遍可以有效防止第二天起床不看注释就写错的尴尬。另外很多人会问prev.next cur.next之后需不需要把cur.next置空不需要。链表节点即使还指着别人只要没有从链表中被引用就相当于被删除了。你在逻辑上把它跳过它自然就不再属于结果链表。实际内存管理由语言自动处理Python或需要你手动释放C/C。LeetCode 题目不管释放但你自己设计代码时可以考虑。5.4 测试用例怎么设计刷题不能只满足于提交通过。我建议任何链表题都至少测试以下六组用例用例输入期望输出测试目的空链表[][]边界单节点[1][1]边界全部重复[1,1,1][]头节点全删开头重复[1,1,2,3][2,3]重复段在头部末尾重复[1,2,2,3,3][1]连续两段尾部删除不重复夹杂[1,2,3,3,4,5][1,2,4,5]正常多段把这几组用例在自己的代码里跑一遍如果都能过基本就稳了。我在本地调试时习惯写一个list_to_linkedlist数组转链表的辅助函数再写一个print_linkedlist打印函数非常方便。很多初学者直接提交看到报错才回头调试那样效率太低。先把调试环境配好再把用例一次性跑完提交基本一次过。调试指针题目还有一个特别实用的技巧在纸上画格子。画一个链表节点的盒子链把 prev、cur、cur.next 都用小箭头标出来然后一步步模拟。我曾经花一晚把 82 题画了四五十个状态图之后所有链表题都不再虚了。这个技巧听起来“土”但真的比盯着代码空想快很多。有一个我在实际面试里被问到过的变体如果链表是“非严格降序”但仍然是排序的只是重复元素不相邻呢那这题就不能用一次遍历了。所以遇到变形题先确认“重复元素是否必然连续”如果连续就用这道题的解法如果不连续需要先统计频率。这一点也值得和候选人讨论。回到 82 题本身。说实话我第一次做这道题时也踩了 prev 不更新的坑后来是把“有重复段不移动 prev没重复才移动”写进代码注释里才算彻底根治。做题最大的收获不是背下这个解法而是深刻理解了一个原则在删除链表中某一段节点时前驱指针必须指向“确定不会被删的节点”否则后续操作会失去锚点。如果你正在准备面试我建议你用 82 题作为链表类题目的“自测题”能不能在 5 分钟内写出无 bug 的迭代解法能不能讲清楚为什么用哑节点能不能说出“删除重复段之后 prev 为什么不移动”能不能画出1 - 1 - 2 - 2 - 3每一步指针变化如果这些都能做到链表删除这一关就算真的过去了。最后再分享一个我常用的本地调试小技巧在写 ListNode 的__str__方法时把“当前值 指向的值”打印出来比如node.val(-next.val)这样在追踪循环时能直观看到指针关系的变化比只看数值有用得多。把这个技巧用在 82 题上你很快就能理解为什么那几行指针操作能满足所有边界情况了。