删除排序链表重复元素II：哑节点双指针一次遍历整段删除

链表题里有一类分支特别膈应人就是把某种元素从链表中彻底抹掉而不是留一个。删除排序链表中的重复元素 II第 82 题就是这一类里的典型代表它要求把所有出现过重复的节点一个不留地删掉只保留在链表中只出现一次的值。很多人第一次写这道题在本地跑几个用例感觉没问题一提交就被头节点被删、连续三个以上重复、链表末尾重复这几类数据打回来。这篇文章我不打算只给你一份能过的代码而是把这道题从题意辨析、方案选型、指针职责划分、逐行实现、手动推演到排错调试的整条链路摊开讲。适合刚刷到链表专题、被哑节点绕晕的新手也适合写过一版但总在边界上翻车的朋友。核心关键词就是删除排序链表中的重复元素、哑节点、双指针、一次遍历下面开始一层层拆。1. 先把题意嚼碎删的到底是哪些节点1.1 一句话规则背后的三个反例题目的规则用一句话概括只要某个值在链表里出现了两次及以上这个值对应的所有节点全部删除只出现一次的值节点保留。听起来简单但真正写代码时全部删除这四个字会被很多人下意识读成重复的只留一个。我用三个反例说明差别。输入1 - 2 - 2 - 3正确输出是1 - 3而不是1 - 2 - 3输入1 - 1 - 1 - 2正确输出是2三个 1 全部消失而不是留一个 1输入1 - 1正确输出是空链表连头都不剩。这三个例子覆盖了重复段在中间、在头部、整条链表都是重复这三种形态写完之后必须拿它们各跑一遍。顺带说一句如果你看到过重复元素只保留一个的版本那是另一道题第 83 题。两道题的代码骨架长得极像但删除逻辑差了一个while循环的位置很容易串味。我的习惯是做完一道就在注释里写清楚本题是全删避免隔天回来改错版本。1.2 有序这个前提到底帮你省掉了什么题目名字里排序链表四个字不是装饰。如果链表无序你要判断某个值是否重复就必须先完整遍历一遍做计数或者用哈希表记录出现次数空间复杂度立刻从 O(1) 涨到 O(n)。而有序意味着相同的值必然挨在一起形成一段一段的连续区间。这个性质带来的直接好处是你只要盯住当前节点和它的下一个节点值是否相等就能判断当前节点是否属于重复段。因为有序不可能出现1 - 2 - 1这种隔空重复也就不需要在内存里记住1 出现过没有。换句话说有序把全局去重这个需要额外空间的问题降维成了局部相邻比较这个只需要两个指针的问题。理解这一点你就明白为什么最优解是 O(n) 时间、O(1) 空间——不是你优化出来的是题目条件白送的。很多人背代码背不下来就是因为没想通这层因果只记住了要比较 cur 和 cur.next。1.3 动手前必须列全的边界清单我在纸上写这道题之前会先列一张边界清单写完代码逐条对。这张单子长这样场景输入示例期望输出考察点空链表nullnull循环入口判空单节点11不进入删除分支两节点相同1 - 1空头节点被删返回值不能用 head两节点不同1 - 21 - 2正常保留重复段在头部1 - 1 - 22哑节点存在的意义重复段在尾部1 - 2 - 21prev 的 next 要置空整条全重复5 - 5 - 5空内层循环走到 null多段重复1 - 1 - 2 - 3 - 32连续处理两段无任何重复1 - 2 - 31 - 2 - 3原样返回这张表不是形式主义。我见过太多人代码逻辑是对的但return head这一句让重复段在头部的用例直接挂掉也见过内层循环写while (cur-next ...)导致末尾重复段删不干净。每一条都是真实存在的坑后面第 5 章会逐条展开。2. 三条技术路线怎么选哈希、双指针、递归2.1 哈希计数法思路最直白代价是多一块内存拿到删除所有重复值这个需求最符合直觉的做法是两趟扫描第一趟遍历整条链表用一个哈希表记录每个值出现的次数第二趟再遍历一次遇到计数大于 1 的节点就跳过只把计数等于 1 的节点接回新链表。这个思路的好处是几乎不需要思考指针的移动顺序也不需要处理重复段有多长的问题代码写出来像流水账很难写错。对于无序链表这甚至是唯一的常规解法。但放在这道题上它有两个明显的短板。第一个是空间。哈希表要存所有不重复的值最坏情况链表里没有任何重复要存 n 个键空间复杂度 O(n)和题目希望的 O(1) 差了一截。第二个是它完全没用上有序这个条件面试官看到这种写法通常会追问一句能不能不用额外空间你还得再写一版双指针。所以我把它定位成兜底方案面试时先口头讲一句可以用哈希计数做到 O(n) 空间然后立刻接但有序条件允许我们做到 O(1)这样反而显得你想得全。用 Python 写出来大概是这样仅作为思路参考def deleteDuplicates_hash(head): # 第一趟统计每个值出现的次数 count {} node head while node: count[node.val] count.get(node.val, 0) 1 node node.next # 第二趟只保留计数为 1 的节点 dummy ListNode(0) tail dummy node head while node: if count[node.val] 1: tail.next node tail node node node.next tail.next None # 关键断开尾部残留的旧连接 return dummy.next注意最后那句tail.next None。如果省略它新链表的尾巴可能还指向原来的后续节点导致输出里混进本该删掉的元素甚至形成环。这个坑在链表题里非常普遍凡是重新拼一条链表的写法收尾都要手动断链。2.2 一次遍历双指针这道题该给的答案真正的标准解法只需要一趟遍历靠两个指针prev和cur配合外加一个哑节点。核心思想是prev永远指向最后一个确认要保留的节点cur负责在前面探路检查自己是不是重复段的一员。如果cur和cur.next的值不相等说明cur是个独苗可以放心保留于是把prev移到curcur往前走一步。如果两者相等说明cur踩进了重复段此时记住这个值用一个内层循环把整段连续相同的节点全部跳过然后让prev.next直接指向跳过之后的第一个节点——这一步是整段摘除而不是删掉其中一个。这个方案的优势很明显时间 O(n)每个节点最多被访问两次外层一次、内层一次空间 O(1)只用了两个指针和一个哑节点。它同时利用了有序性和链表可原地改指针的特点是这道题的最优形态。写的时候有一个细节必须想清楚内层循环结束后prev不能动。因为prev后面接上来的新节点还没被检查过它自己可能又是一段重复的开头。这一点是新手最容易出错的地方我放在 3.4 节单独讲。2.3 递归写法短是短栈深度是隐患递归版本的代码通常只有七八行看起来很优雅。思路是先看当前节点和下一个节点是否相同如果相同就记住这个值一路跳过所有相同节点然后对跳过之后的链表递归如果不同就让当前节点的 next 指向递归处理后的结果。def deleteDuplicates_rec(head): if not head or not head.next: return head if head.val head.next.val: v head.val while head and head.val v: # 整段跳过 head head.next return deleteDuplicates_rec(head) else: head.next deleteDuplicates_rec(head.next) return head这段代码逻辑是对的但我不建议在工程场景里用它。链表长度可能是十万级递归深度跟着线性增长遇到超长链表有栈溢出的风险。而且递归版在调试时很难打印中间状态出错了只能靠脑补调用栈。我的建议是面试时如果时间紧张可以先写递归版把思路讲清楚说明这里可以改成迭代把空间降到 O(1)然后动手写迭代版。这样既展示了思维过程又体现了工程意识。如果面试官直接要最优解那就别绕直接上双指针。2.4 三种方案横向对比维度哈希计数法双指针迭代递归时间复杂度O(n)O(n)O(n)空间复杂度O(n)O(1)O(n) 栈空间是否依赖有序不依赖依赖依赖代码行数中等中等短出错概率低尾部易漏断链中指针移动顺序中边界递归适用场景无序链表通用面试与工程首选讲思路、短链表超长链表风险无无栈溢出这张表的核心信息是只有双指针同时满足线性时间和常数空间其余两种都是特定场景下的取舍。你在写解题笔记时把这张表贴在代码上方下次复习扫一眼就能回忆起全部取舍逻辑比反复读代码高效得多。3. 哑节点加双指针把每一行代码掰开看3.1 为什么非得挂一个哑节点先回答一个高频疑问为什么不能直接用 head 开始操作因为头节点本身可能就是重复段的一部分会被删掉。比如1 - 1 - 2最终返回的应该是从2开始的链表原来的 head 已经不在结果里了。如果你全程用 head 做返回值这个用例必挂。哑节点的作用就是造一个永远存在、永远不会被删的锚点。它挂在真正的头节点前面值随便填通常填 0 或 -1不参与业务判断。这样无论真正的头节点被删几次哑节点的 next 都会自动指向新的头你只需要在最后返回dummy.next即可。这和建筑工地上的脚手架是一个道理楼盖好后脚手架要拆但施工期间它撑着所有结构。哑节点就是链表题的脚手架凡是涉及头节点可能变化的题我都会条件反射地先挂一个上去包括删除节点、合并链表、反转链表这些经典题型。需要提醒的是C 里哑节点通常声明成栈上的对象ListNode dummy(0, head)然后取地址dummy使用Java 和 Python 直接 new 一个对象即可。不要在 C 里用new分配哑节点否则还要手动释放白白增加内存管理负担——反正函数返回后栈对象自动销毁指针早就不用了。3.2 prev 和 cur 各管什么职责不能混双指针版本里两个指针的分工必须界定清楚混着用必然出错。我的定义是cur探路指针指向当前正在检查的节点。它的任务是判断自己是不是重复段的一员。prev施工指针指向最后一个已经确认要保留的节点。它的任务是执行删除动作——通过修改prev.next把不要的节点摘掉。关键在于prev永远只在确认某个节点要保留时才移动其他时候原地不动。这个约束一旦破掉就会出现该删的没删干净或者把不该删的节点也摘了这两类错误。举个具体场景加深印象。链1 - 2 - 2 - 3初始prev dummycur 1。第一步比较 1 和 2不相等于是prev移到 1cur移到第一个 2。第二步比较 2 和 2相等进入删除分支此时prev停在 1 不动内层循环把两个 2 全部跳过cur落到 3然后prev.next cur也就是让 1 直接指向 3。第三步比较 3 和 null不相等prev移到 3cur变成 null循环结束。整个过程里prev移动了两次删除动作只发生了一次但一次删掉了两个节点。这就是整段摘除的含义也是这道题和只保留一个版本最本质的区别。3.3 完整实现三版代码对照着看C 版本struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* deleteDuplicates(ListNode* head) { ListNode dummy(0, head); // 哑节点挂在头前面 ListNode* prev dummy; // 最后一个确认保留的节点 ListNode* cur head; // 探路指针 while (cur) { if (cur-next cur-next-val cur-val) { int v cur-val; // 记下重复值 while (cur cur-val v) { // 整段跳过 cur cur-next; } prev-next cur; // 整段摘除 } else { prev cur; // 保留 cur cur cur-next; } } return dummy.next; }Java 版本public ListNode deleteDuplicates(ListNode head) { ListNode dummy new ListNode(0, head); ListNode prev dummy; ListNode cur head; while (cur ! null) { if (cur.next ! null cur.next.val cur.val) { int v cur.val; while (cur ! null cur.val v) { cur cur.next; } prev.next cur; } else { prev cur; cur cur.next; } } return dummy.next; }Python 版本class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def delete_duplicates(head): dummy ListNode(0, head) prev, cur dummy, head while cur: if cur.next and cur.next.val cur.val: v cur.val while cur and cur.val v: cur cur.next prev.next cur else: prev cur cur cur.next return dummy.next三版代码骨架完全一致差异只在语法层面。C 用nullptr判空Java 和 Python 用 null/NoneC 的哑节点在栈上Java 和 Python 在堆上。我建议你把三版都手敲一遍尤其是 C 那一版指针符号多敲的过程中会强迫你想清楚每一步拿到的是节点还是地址。代码里有两个细节值得单独标注。第一cur-next 这个前置条件不能省略否则当cur是尾节点时cur-next-val会直接解引用空指针。第二内层循环的判空条件写成cur cur-val v不是cur-next ...因为你要跳过的是cur自己而不是它的下一个。3.4 删除分支结束后prev 为什么不能动这是整道题最容易写错的地方我单独拿一节讲。先看一个错误写法// 错误示范删除分支里多写了一行 if (cur-next cur-next-val cur-val) { int v cur-val; while (cur cur-val v) cur cur-next; prev-next cur; prev cur; // 错在这里 cur cur-next; // 这里也错 }错在哪假设链是1 - 1 - 2 - 2 - 3。第一轮删掉两个 1 之后cur落在第一个 2 上。如果此时你把prev也移到了这个 2 上那么下一轮发现 2 是重复的、需要整段删除时prev.next cur这一句就变成了让 2 指向 3而 2 本身已经被当作保留节点接在结果里了最终输出会变成2 - 3多出一个本该删掉的 2。正确的做法是删除分支结束后prev原地不动cur已经指向新的候选节点下一轮循环继续检查它。只有当cur被确认是独苗、走 else 分支时prev才往前挪。用一句话总结这条规则prev 只在确认保留时前进在删除时原地待命。我把这句话写在了自己的链表模板注释里做同类型题目时直接套用能省掉大量调试时间。4. 手动推演拿几组数据把指针走一遍4.1 主用例逐步推演光看代码容易产生我懂了的错觉真正把每一步的指针状态写出来才能发现理解上的空洞。我用1 - 1 - 1 - 2 - 3 - 3 - 4这组数据走一遍它同时包含头部重复段、中部独苗、尾部重复段三种情况。初始状态dummy - 1 - 1 - 1 - 2 - 3 - 3 - 4prev dummycur 第一个 1。轮次cur 值判断内层跳过prev.next 指向prev 位置下一轮 cur11与下一个相等跳过三个 12dummy222与下一个不等无22333与下一个相等跳过两个 342444下一个为空无44null第一轮结束后链表变成dummy - 2 - 3 - 3 - 4三个 1 被整段摘掉。第三轮结束后变成dummy - 2 - 4两个 3 被摘掉。第四轮 4 是独苗prev移到 4cur变成 null循环退出返回dummy.next即2 - 4。把这个表格手写在纸上比读十遍代码有用。我刷题时有个习惯凡是涉及两个以上指针移动的题一定在草稿纸上画表格标注每一轮三个变量的值。这个动作看起来慢但能让你在写代码前就把逻辑跑通实际敲代码的时间反而缩短。4.2 三个极端用例的验证第一个极端空链表。head nullcur一开始就是 nullwhile 循环一次都不进直接返回dummy.next也就是 null。正确。第二个极端1 - 1。初始prev dummycur 第一个 1。判断成立记下 v 1内层循环跳过两个 1cur变成 nullprev.next null哑节点的 next 被置空。循环结束返回 null。正确。这个用例专门验证头节点被删光的场景用return head的写法在这里必挂。第三个极端5 - 5 - 5。内层循环连跳三次cur到 nullprev.next null返回空。正确。这个用例验证的是重复段长度超过 2时内层循环能否完整跳完如果内层写成if而不是while这里只会跳过一个 5输出会变成5直接暴露错误。第四个补测1 - 2 - 2验证尾部重复。第一轮比较 1 和 2 不等prev移到 1cur移到第一个 2第二轮判断 2 和 2 相等内层跳到 nullprev.next null链表变成1 - null返回 1。正确。这一条验证的是prev.next cur在cur为 null 时也能正确断链不需要额外写判断。4.3 自己造测试用例的套路随机构造用例容易漏掉关键形态我一般按重复段的位置 × 重复段长度这个二维矩阵来造。位置维度分三种头部、中部、尾部。长度维度分三种长度 2、长度 3、长度超过 3比如 5。再加上多段重复并存和完全无重复两个特殊形态一共 11 条用例基本能覆盖所有分支。具体清单可以这样组织头部重复的1 1 2、1 1 1 2、1 1 1 1 1 2中部重复的1 2 2 3、1 2 2 2 3、1 2 2 2 2 2 3尾部重复的1 2 2、1 2 2 2、1 2 2 2 2 2多段并存的1 1 2 3 3 4 4 4 5完全无重复的1 2 3 4 5。再加空链表和单节点一共 13 条。每次改完代码把这 13 条跑一遍比对着别人的答案改要可靠得多。我在本地写了个小程序把这 13 条用例和期望结果写死在数组里跑一次全绿才算过。这套流程用在别的链表题上也一样只是期望结果要换。5. 踩坑实录这些错我基本都犯过5.1 高频错误速查表现象可能原因定位方法修法运行时崩溃cur-next未判空就取 val打印 cur 地址判断条件加cur-next 头节点重复时结果多一个返回了head而不是dummy.next用1 1 2测试改为返回哑节点 next三个以上连续重复只删了一个内层误用if用1 1 1 2测试改成while删除分支后少了一个节点删除后多移了prev和cur用1 1 2 2 3测试删除分支只改 prev.next尾部残留多余节点忘记把prev.next置空用1 2 2测试内层跳完后正确赋值死循环内层循环条件写错cur 不前进加计数打印检查cur cur-next是否执行输出链表成环复用了旧节点的 next 没断遍历计数超长尾部手动tail.next null这张表是我这些年断点调试攒下来的按现象 → 原因 → 定位 → 修法四列组织出问题时从现象倒查比从头读代码快得多。建议你也在自己的笔记里维护一份每踩一个新坑就加一行。5.2 空指针到底在哪一步炸空指针是链表题的头号杀手这道题里有两个高发位置必须背下来。第一个位置是外层判断cur.next.val cur.val。当cur是尾节点时cur.next是 null直接取.val立刻崩溃。修法很固定判断条件写成cur.next ! null cur.next.val cur.val把判空放在最前面利用短路求值挡住后面的取值。第二个位置是内层循环的条件。有人写成while (cur.next cur.next.val v)看起来也判空了但语义错了——它检查的是下一个节点而你要跳过的是当前节点。正确的写法是while (cur cur.val v)判的是cur自己。这两种写法在1 1 2上结果一样但在1 1上就会分出胜负前者内层只跳过一次cur停在第二个 1 上后面虽然也会被删但如果链更长、重复段是最后一段就会出现残留。我的经验是凡是在循环里对指针解引用先问自己这个指针在这一步有没有可能是 null。想不清楚就用打印验证别硬猜。链表题的崩溃基本都是确定性的跑一个最小用例就能复现远比猜快。5.3 调试打印与本地自测的方法链表题不像数组那样能直接打印看内容所以我建议每个写链表题的人先写两个辅助函数一个是把链表转成列表或字符串用于打印另一个是安全地取链表长度带步数上限防止成环。遍历打印大概是这样def show(head, limit50): out, node, steps [], head, 0 while node and steps limit: out.append(str(node.val)) node node.next steps 1 if steps limit: out.append(...可能成环) return - .join(out)有了它在循环的每个分支里加一句打印比如print(f轮次{i}: prev{prev.val}, cur{cur.val if cur else None})跑一组小数据输出和你在纸上推演的表格一对哪里偏了一眼就能看出来。我调这道题的时候就是靠打印发现自己在删除分支里多移了prev——纸上推演时没注意打印出来第二轮prev停在 2 上立刻定位到问题。成环检测也很有用。如果提交后提示超时先别急着怀疑复杂度用上面那个 limit 函数跑一下很可能是指针接错了形成了环遍历永远走不到头。这是链表题特有的故障形态数组和字符串题不会遇到。6. 这道题往外延伸的几个方向6.1 兄弟题与变体把这道题吃透一组同族题基本可以无痛拿下。第一类是重复只保留一个的版本删掉内层循环遇到相邻相等就把prev.next指到cur.next其余逻辑复用。第二类是无序链表去重回到哈希法或者排序后再套本题。第三类是删除指定值的所有节点连是否相邻都不用管遇到目标值直接摘注意哑节点同样必须加。还有一类变体值得单独练要求删除重复后返回被删元素的集合。这类题在双指针基础上加一个收集容器即可难度不大但会迫使你重新梳理一遍分支逻辑对巩固记忆很有帮助。我在练习时会把这几道题排在一起连续做中间不查题解。因为它们的骨架高度相似连续做能强迫你主动分辨差异点——这里要不要留一个这里判不判断有序这种对比记忆比单题背代码有效得多。6.2 链表题通用手感三个动作固定下来做完这道题我沉淀了三个固定动作现在做任何链表题都会先做一遍。第一个动作先挂哑节点。只要题目可能改动头节点先写上dummy返回值统一写dummy.next不要在这上面纠结。第二个动作先画图再写码。两个以上指针的题一定在纸上把初始状态画出来标注每个指针的位置然后手动走两轮。这个动作花不了两分钟但能省掉半小时的调试。第三个动作写完立刻跑边界四件套——空链表、单节点、头重复、尾重复。这四条覆盖了链表最容易出问题的四个位置跑通了再去提交通过率会高很多。我个人的体会是链表题的难度从来不在算法本身而在你对指针当前指向谁、指针之间的相对位置是否被破坏这件事的掌控力。这道 82 题看似在考去重实际在考你能不能在心里维护一张实时的指针状态图。等你能不画图就把1 - 1 - 1 - 2 - 3 - 3 - 4的每一轮状态说出来链表这个专题基本就通了。