1. 题目拆解先弄懂它在考什么力扣82题“删除排序链表中的重复元素 II”这些年一直保持着挺高的热度原因很简单它和83题长得像但坑却多得多。83题要求重复元素保留一个属于“去重”而82题要求把重复元素全部删掉一个不留属于“消灭”。这两者的思维量完全不同。题目本身的描述很克制给定一个已排序的链表删除所有含有重复数字的节点只保留原始链表中没有重复出现的数字。比如链表是 1-2-3-3-4-4-5结果应该是 1-2-5。再比如 1-1-1-2-3结果应该是 2-3。很多人在一开始会陷入一个误区把这道题当成83题的简单变体想着“边遍历边删除多余节点”就行。但真正动手写代码后就会发现难点根本不是“找到重复”而是“在单链表里当你发现某一段值重复时怎么把整段都摘掉同时不影响后续遍历”。单链表只能单向走拿到当前节点时你没法回头看前一个节点是谁。而删除一段区间恰恰需要你精准地操作区间前驱节点的next指针。这一进一出就把题目从一个“遍历题”变成了“指针维护题”。另外还有一层隐藏考点头节点也可能是重复的。当链表开头就出现重复时你连“前驱节点”都没有这迫使你必须引入虚拟头节点dummy node来处理边界。很多面试官就是通过这道题考察候选人对边界情况敏感度的虚拟头节点用不用、怎么用基本能直接看出有没有系统刷过链表题。所以我的建议是在做这道题之前把单链表的基本操作彻底吃透包括不带头结点的单链表插入、删除、逆序最好能熟练到不用过脑就能写出来。这道题本质上不是在考“删除算法”而是在考你“对链表结构的肌肉记忆”。2. 三种主流解法从哈希计数到递归层层递进2.1 解法一哈希表计数最容易理解的一条路第一个能想到的解法通常是用哈希表统计每个值的出现次数。第一遍遍历链表把每个节点的值存进哈希表value记录出现次数第二遍再遍历一次只保留下出现次数为1的节点。这个思路非常直观属于“用空间换清晰度”的典型。具体的实现步骤是这样的定义一个 unordered_mapC/ dictPython第一遍遍历统计频率创建虚拟头节点 dummyprev 指向 dummy第二遍遍历原链表如果当前节点的值在哈希表中次数大于1直接跳过否则接入新链表。这个解法的优点是代码几乎不会出错逻辑特别适合面试时当作“保底方案”。缺点是额外使用了O(n)的空间并且遍历了两次链表。如果面试官要求O(1)额外空间这个方案就不满足要求了。我个人建议如果是笔试场景先用哈希计数拿满分没有问题但如果是面试场景最好紧接着把双指针/虚拟头节点的方案写出来因为那才是面试官真正想看你掌握的。哈希解法在面试里更像是“热身答案”而不是“终版答案”。2.2 解法二虚拟头节点 三指针面试标准答案这是我要重点展开的解法也是目前社区里最推荐的做法。思路一句话就能概括因为链表已经排好序重复元素一定连续出现所以我们用一次遍历跳过所有值相同的连续节点段。核心技巧是引入虚拟头节点。为什么必须引入考虑一个极端情况链表是 1-1-2-3第一个节点本身就是重复节点删除后链表头要变成2。如果不引入虚拟头节点你需要单独写逻辑来更新头节点代码会多出一堆if判断。而引入dummy后dummy-next始终指向最终的头节点删除逻辑就统一了。三指针的具体分工是dummy指向结果链表的头同时作为删除操作的起点prev始终指向“已确认不会删除的最后一个节点”cur当前正在检查的节点next用来探测后续节点是否与cur重复。判断逻辑也很清爽如果 cur-val ! next-val说明cur不是重复节点prev可以放心地移动到cur如果 cur-val next-val说明cur属于重复段就让next一直往前走直到遇到值不同的节点然后把 prev-next 直接指向这个新节点相当于把整段重复都跳过了。这里有一个很容易出错的地方当跳过重复段后prev 不应该移动因为新的 next 节点还没被确认是否安全。必须等下一轮循环确认它不重复后prev才能挪过去。很多人的代码在这步写错结果要么是误删了要么是死循环。2.3 解法三递归一行核心逻辑揭示本质递归解法代码量最少但对理解能力要求最高。它的思想是处理当前节点时如果它和下一个节点值不同那当前节点可以保留它的next递归处理如果相同就跳过这一整段重复值直接对第一个不重复的节点递归。伪代码大概是这样的deleteDuplicates(head): if head为空或head-next为空: return head if head-val ! head-next-val: head-next deleteDuplicates(head-next) return head else: cur head-next while cur 且 cur-val head-val: cur cur-next return deleteDuplicates(cur)这个解法的关键理解点在于当遇到重复段时整个 head 都不能要了所以递归入口直接变成 cur第一个值不同的节点。换句话说递归在“丢弃节点”这件事上比迭代解法更彻底它压根不保留任何重复段的中间指针。但递归也有代价递归深度等于链表长度如果链表特别长比如几万个节点有栈溢出的风险。面试时可以提一句“递归思路清晰但迭代版本更稳”展示你对这两种方案的权衡思考。3. 双指针迭代解法从伪代码到逐行实现3.1 C 完整实现与逐行注释我平时刷题主力用的就是C。下面这份实现我调试过很多遍已经比较稳定直接贴出来供参考ListNode* deleteDuplicates(ListNode* head) { if (!head || !head-next) return head; ListNode* dummy new ListNode(0); dummy-next 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; } // 此时cur指向重复段的最后一个节点 // prev-next 直接指向重复段后面的第一个节点 prev-next cur-next; } else { // cur 不是重复节点prev 向前移动 prev cur; } cur cur-next; } return dummy-next; }几个关键的细节我在这个地方必须强调第一内层 while 循环结束后cur 停留在重复段的最后一个节点上而不是第一个不重复节点。这一步很多新手会算错导致 prev-next 指向了错误位置。建议动手画一下假如链表是 1-2-2-2-3cur开始指向第一个2内层循环结束后cur指向最后一个2此时 prev-next cur-next 才刚好指向3。第二当进入“删除分支”后prev 没有更新这非常关键。因为 prev-next 已经被直接接到了一个未知节点上这个新节点有可能是下一段重复的开头必须在下一轮循环中判断。如果你在这里手一滑写了 prev cur那下一轮 cur cur-next 就会导致 prev 指向一个已经被删除的节点链表结构直接断掉。第三最后返回的是 dummy-next而不是 head。因为 head 完全有可能是重复节点被删除掉了此时 head 已经不在结果链表中。这是新手最容易犯的错代码逻辑全对但返回了旧 head导致结果错误。3.2 Python 实现写法更简洁但陷阱不变Python版本的逻辑和C完全一致只是语法更轻量class Solution: def deleteDuplicates(self, head: Optional[ListNode]) - Optional[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 else: prev cur cur cur.next return dummy.next很多人在 Python 里会犯的一个低级错误是忘记处理 cur.next 为 None 的情况直接写 cur.val cur.next.val在链表末尾抛空指针异常。上面这段代码里我每一处都加了 cur.next 的判断这就是从报错堆里换来的教训。另外Python 的 ListNode 定义里其实已经带了一个可选的 next 参数__init__(self, val0, nextNone)所以创建 dummy 节点时可以写ListNode(0, head)一行搞定不需要分开赋next。这个小细节能让你笔试时写得快几秒顺便显得对语言更熟悉。3.3 指针移动的全过程推演用具体例子走一遍理论写再多不如用一个完整例子在纸上推一遍。拿最常见的测试用例 1-2-3-3-4-4-5 来说初始化dummy(0)-1-2-3-3-4-4-5prevdummycur1。第一轮cur1cur.next2值不相等进入else分支prev从dummy移到1。cur移到2。第二轮cur2cur.next3值不相等prev从1移到2。cur移到3。第三轮cur3cur.next3值相等进入if分支内层while让cur跑到第二个3。此时cur指向第二个3prev-next cur-next即2-4。链表变成 dummy-1-2-4-4-5。注意此时prev仍然指向2没有移动。cur在循环末尾移动到4。第四轮cur4cur.next4值相等内层while让cur跑到第二个4。prev-next cur-next即2-5。链表变成 dummy-1-2-5。cur移动到5。第五轮cur5cur.next为null进入else分支prev从2移到5。cur移到null循环结束。最终返回 dummy-next即 1-2-5。整个过程非常清晰核心思想就是“发现了重复段让prev绕过整段”。这个推演我建议你自己在纸上画一遍即便你觉得自己已经会了。因为链表的指针移动和数组下标移动完全不是一回事画过一遍之后你对 prev 何时移动、cur 何时移动的理解会彻底固化。4. 链表基础补课不带头结点的单链表为何是这道题的“隐形考点”4.1 带头结点和不带头结点的核心区别热词里反复出现“不带头结点的单链表”和“单链表的基本操作实验”说明这道题在课堂和面试里经常被拿来和课本基础绑定考察。先把这个概念理清楚。带头结点的链表会有一个额外的头结点dummy在真正的第一个数据节点之前。它的作用有两个一是统一插入、删除逻辑对第一个位置的操作不用特殊处理二是头结点的指针域可以承载链表长度等信息不过在力扣里一般不这么玩。不带头结点的链表头指针直接指向第一个数据节点。这种结构更省空间也更接近“链表是啥就长啥样”的直觉。但它的缺点就是当你需要删除第一个节点时必须更新头指针本身否则整个链表就丢了。有没有发现这和我们前面讲虚拟头节点的动机一模一样力扣82题默认给的就是不带头结点的链表head就是第一个数据节点所以头部删除问题必须自己想办法。引入dummy本质上是把“不带头结点的链表”原地升级成了“带头结点的链表”从而复用一套整齐的删除逻辑。这个认知非常重要。很多人刷了几百道题遇到链表题永远靠背模板却不知道为什么模板长这样。一旦理解了“dummy节点是为了把不带头结点变成带头结点”你遇到所有需要动头节点的链表题都能举一反三。4.2 为什么链表题在嵌入式场景里特别受重视热词里出现了“嵌入式链表代码示例”这提醒我们链表不是只在力扣刷题里有用。在嵌入式系统、操作系统内核、底层驱动里链表的使用频率非常高。嵌入式场景里最典型的是侵入式链表即链表节点嵌在结构体内部。比如一个内核驱动要管理一串设备节点它可能这样定义struct device_node { int id; char name[32]; struct list_head list; // 嵌入式链表节点 };这里的 list 不是指向“另一个设备节点结构体”而是指向结构体内部的链表指针成员。这种做法的优势在于同一个结构体可以被挂载到多个链表里比如一个按ID排序的链表、一个按优先级排序的链表它们互不干扰靠的就是结构体内多个 list_head 成员。回到力扣这道题它在嵌入式场景里的意义在于“遍历和删除的边界处理”。真实驱动代码里删除一个设备节点时如果处理不好前驱节点的回填轻则链表断裂重则内核崩溃。所以很多嵌入式岗位的面试反而会拿这种基础链表题来筛人不是为了刁难是为了确认你具备“操作底层数据结构时不犯低级错误”的素质。顺带一提嵌入式里常常使用循环单链表。循环链表在遍历时判断结束的条件从“指针为空”变成了“指针重新回到头节点”。如果你想用82题的思路去处理循环链表结束条件得多写一条否则会陷入死循环——这个区别建议你自己写代码体会一下属于笔试里偶尔会出现的变体坑。4.3 C结构体链表语法速览如果你对C里定义链表节点还不太熟这里随手列一下默认的标准写法struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };力扣的 C 环境里已经帮你定义好了这套结构体你只需要直接用。但如果你在自己的本地环境里练习得手动把这三行写上去。有个小细节标准写法里的三个构造函数是重载关系分别适配无参、一个参数、两个参数的初始化场景。面试手写链表时如果面试官要求你自己定义结构体三个构造函数写全是一个加分项说明你对默认参数和初始化列表是理解的。对应地Python 环境里的定义是class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextPython 的默认参数把三个构造函数合并成了一个写起来比 C 少一截。这也是很多从 Python 转 C 刷题的人初期卡壳的原因C 结构体初始化必须显式传参忘了传 next 的话它是未定义的野指针属实是个大坑。5. 边界条件与特殊输入把用例测到让人放心5.1 六种必测的边界输入链表题的边界条件永远比正常逻辑更容易出错。我把这道题值得单独测一遍的输入整理了一下建议你提交代码前逐条过一遍输入链表期望结果测试意图空链表[][]最基础的防御单节点[1][1]无重复原样返回全部重复[1,1,1][]整条链表被删空前面全重复[1,1,2,3][2,3]头节点要被更新后面全重复[1,2,2,2][1]尾部整段删除无重复[1,2,3][1,2,3]确认不误删这里最值得警惕的是“全部重复”这种情况。链表是 1-1-1你的代码应该返回空链表。在双指针解法里最终会得到 dummy-next 为 nullptr然后返回空链表逻辑是对的。但我见过不少初学者在这一步报空指针异常原因是循环结束后又试图访问 cur-next——链表都空了哪来的 next 可访问。解决方法是循环条件里始终判 cur而不是 cur-next所有对 next 的访问都先确保 cur 不是空。另一个容易被忽略的场景是“重复段恰好出现在链表末尾”。比如 1-2-3-3-3。内层 while 会一直走到 cur-next 为 nullptr 才停此时 prev-next nullptr链表被从中间截断后面的重复节点全部被丢弃。这个操作本身没问题但如果你在内层循环里不小心把判断条件写成 cur-val cur-next-val而 cur-next 已经为空就会直接炸掉。所以内层 while 和外层 while 一样都必须先判 cur-next 非空。5.2 内存释放问题这是本地调试和面试都要注意的点C 选手在本地练习时记得要释放被删除节点的内存否则会内存泄漏。力扣的在线判题系统不检查内存泄漏但你用本地编译器跑测试时Valgrind 会毫不留情地报出来。更麻烦的是LeetCode 上通过提交的代码如果你自己写个 main 函数在本地跑完不释放内存退出时不会报错但如果你把代码搬到真正的工程里这就会成为问题。有一种简单的释放方式在跳过重复段时先把要释放的节点暂存到一个临时变量等指针操作完成后统一 delete。不过作为刷题我一般不在解题代码里写 delete原因有两个一是 delete 会让代码变得啰嗦影响阅读二是力扣的测试环境会统一回收内存没有必要。但在面试中如果有人问起“这些被跳过的节点你打算怎么处理”你能说出“本地测试需要delete在线判题可以不delete”这个区别会显得很有工程经验。6. 常见问题与排查技巧实录6.1 问题一为什么我的代码会陷入死循环死循环是链表题里最经典也最磨人的问题。82题里最常见的一种死循环写法是在“跳过重复段”分支里循环结束后没有让 cur 前进或者让 prev 错误地停留在原地导致下一轮循环又重复处理同一段节点。排查死循环的经验只有一条死循环的本质是“循环变量没有向结束条件前进”。在外层 while 里前进条件是 cur cur-next。你只需要检查每一条执行路径是否都执行了这个赋值。分配一个随机小链表在关键步打印 cur-val观察它是否在反复打印同一个值基本上就能定位。还有一个我实际踩过的坑把内层 while 的指针移动当成外层 while 的移动。内层 while 让 cur 移动到重复段末尾外层循环末尾的 cur cur-next 是在这个基础上再走一步。如果你忘了这一点在某些情况下 cur 会多走一步跳过正在等待判断的节点导致结果漏掉节点或者多保留重复项。这个 bug 非常隐蔽光靠读代码很难发现必须在纸上推演才能看出来。6.2 问题二结果总是多保留一个重复节点典型的症状是输入 1-1-2输出却是 1-2而不是 2。说白了就是重复段只删了一部分没删干净。通常原因是你把内层 while 的起始位置弄错了。正确写法是发现 cur 与 cur-next 值相同后从 cur 开始向后探测探测完成后整段包括cur自己都删掉。但错误写法往往是从 cur-next 开始探测探测结束后 cur 仍然保留了下来——cur 本身是重复的你却没有删除它于是多留了一个。还有一个小概率的原因是 prev 在删除分支里提前移动了。前面反复强调“删除分支里 prev 不能移动”如果违反了prev 可能会停在重复段中间下一轮删除操作就会从错误的位置切断链表结果飘忽不定。6.3 问题三从“看懂”到“一次写对”还差什么后台经常有人私信问思路我都懂为什么自己写的时候还是会卡壳这类问题的根源几乎都是“指针指向”和“值”在脑子里没有分开。链表节点有两个维度的信息节点的值以及节点的位置。很多人在调试时把两者混为一谈比如“cur 是重复的”这句话到底是指 cur 的值等于前一个节点的值还是指 cur 这个对象必须被释放想不清楚代码自然写不利索。我的建议是刻意练习一种说话方式描述指针移动时永远说“prev 现在指向第几个节点”“cur 现在站在哪个位置”而不是“prev 现在是几”。养成这个习惯之后你会发现链表题的调试时间大幅下降因为你能在脑子里精确模拟出每一步之后指针的位置而不是靠运行结果反推逻辑。7. 从这道题延伸开去的刷题心法7.1 链表题的统一解题模板刷多了之后你会有个感觉链表题表面上花样百出但结构其实就那几板斧。虚位以待的 dummy 节点、前后双指针/快慢指针、递归的“信任子问题”思路基本能覆盖80%以上的题。82题恰好把他三个元素都占齐了。我建议你把这道题当作链表题的“母题”来对待。母题的意思是你可以把它延伸成一系列变体来练83题重复元素保留一个怎么改如果链表是无序的先排序再删还是用哈希如果只删除出现次数大于2的保留恰好出现2次的怎么写如果是循环链表且头节点不固定怎么处理每改一个条件你都会重新审视一次自己对“前驱指针”的理解。这样反复练上三五道变体比盲目刷十几道新题更有用。7.2 面试和笔试里的表现策略笔试场景下如果你第一反应是哈希计数没关系先写出来保证 AC 再说时间紧张的时候稳定拿分最重要。AC 之后再回头看一眼自己的代码如果能用双指针优化空间复杂度可以再提交一版。面试场景下则相反。面试官更在乎过程而非结果。建议先快速给出哈希解法的思路框架然后主动说“这个方案空间复杂度O(n)如果要求O(1)空间可以用虚拟头节点加双指针”并立刻在白板上写出优化版。主动展示这种权衡能力比憋出一个完美答案更能给面试官留下好印象。还有一个小经验面试手写链表题时白板空间有限写代码之前先用自然语言说出你要维护哪几个指针、每个指针的职责是什么。说清楚了再动手相当于先做了一次草稿基本不会写乱。不要边想边写链表指针一乱白板代码基本就废了。7.3 本地练习环境与测试小技巧力扣自带的编辑器其实不太适合练习“真正把链表玩明白”。我更推荐你在本地搭一个简单的测试环境写一个createLinkedList函数把数组转成链表再写一个printLinkedList函数这样可以自己构造各种边界用例跑一次就肉眼验证结果。C 本地测试时main 函数大概长这样int main() { vectorint nums {1, 1, 2, 3, 3, 4, 5, 5}; ListNode* head create(nums); Solution s; ListNode* ans s.deleteDuplicates(head); print(ans); return 0; }这看起来很简单但在本地跑通一次比你刷十道题都有用。原因在于你会被迫面对力扣后台帮你隐藏的各种细节怎么申请节点、怎么释放内存、怎么在控制台输出链表这些都是真实工程里绕不开的基本功。7.4 力扣刷题的正确姿势重复训练比题海战术重要热词里提到“力扣刷题攻略”这里多说一句我的个人观点。链表题最适合“间隔重复”的训练方式今天做完82题明天把83题做一遍一周后再回来重新做一次82题。第二次做的时候你会发现很多第一次完全注意不到的细节。通常第一次做你是在“照着思路写”第二次做你是在“验证自己是否真的懂了”。区别很大。尤其是像82题这样的题第二次独立写出来的代码如果和第一次完全一样说明你只是记住了模板没有形成自己的理解。如果写出了不一样的写法比如用递归替代了迭代甚至用哈希替代了双指针那才说明你真正掌握了这道题背后的多种可能。最后分享一个很玄但很真实的现象链表题写到一定量之后突然有一天你会发现所有题都变简单了。那不是因为题目变简单了而是因为你终于习惯了“指针不是值节点不是数据”的思维方式。这种思维一旦建立再遇到复杂的链表操作比如逆置链表、合并多个有序链表、判断环的入口你都能一眼看出它的核心结构。82题就是这个思维转变的绝佳起点值得你花一天时间把它彻底吃透。