前几天群里有位刚转行的同学跑来问我入门链表题刷哪道好我几乎是条件反射地回答——LeetCode 83删除链表中的重复元素。这道题在力扣上标的是“简单”但实际面试里出现频率奇高因为链表问题最考验动手前对指针关系的理解。很多人在数组上如鱼得水一到链表就晕问题就出在没搞懂“节点对象”和“引用”这两个概念。这篇文章就从这道题出发把链表删除类题目的思路、实现、坑位、变形全梳理一遍。无论你是刚开始刷题还是准备面试前复习读完之后再遇到同类题应该会顺手很多。1. 先读懂题目不要被“简单”两个字骗了1.1 题目到底在问什么原题描述非常简洁给定一个已排序的链表的头节点 head删除所有重复的元素使每个元素只出现一次返回已排序的链表。举个例子1 - 1 - 2返回 1 - 21 - 1 - 2 - 3 - 3返回 1 - 2 - 3。这个“已排序”三个字是解题的最关键约束它意味着重复值一定相邻。比如一个链表是 1 - 2 - 2 - 3所有值为 2 的节点堆在一起你永远看不到 2 被 3 隔开的情况。这让问题从“全局去重”变成“相邻去重”难度降了好几个档次。从题目要求看我们只需要保留一个节点。比如重复三次的 1 - 1 - 1最终也要变成单个节点 1。这跟“删除所有重复节点”的 LeetCode 82 不一样后者要求 1 - 1 - 1 这种连续重复的全部删掉结果是空链表。所以在写代码之前先把保留规则刻在脑子里不然很容易写着写着就串题了。1.2 边界条件与输入输出细节这道题最容易丢分的就是边界条件。我整理了几类经常被老手拿来做陷阱的输入你可以拿来自测输入预期输出考察点空链表 head nullnull代码不能一上来就访问 head.next只有一个节点 head 11循环条件是否自然结束全部重复 1 - 1 - 11连续多次删除时指针是否正确头部重复 1 - 1 - 21 - 2头节点本身能否保留尾节点重复 1 - 2 - 21 - 2删除到末尾时是否有空指针正常无重复 1 - 2 - 31 - 2 - 3不能误删正常节点值得注意的是输入是链表节点对象不是数组。这意味着我们不能直接像数组那样用下标访问只能通过 next 指针一个个往后跳。而这个“跳”的过程稍微不留神就会让引用丢失所以下面先把链表的基础操盘手——指针讲透。2. 链表操作的基础为什么这个题需要先理解指针2.1 链表节点与指针关系链表中的每个节点本质上是一个对象里面存了一个值 val和指向下一个节点的引用 next。在 Java、Python、C 里这个引用就是“指针”或“对象引用”。比如我们有这样一个链表1 - 2 - 3实际上是用三个对象串起来每个对象通过 next 指着下一个对象。很多初学者画链表图时习惯把“节点”和“指针”混在一起。其实你可以把链表想成一根长长的铁链每个节点是环next 就是环与环之间的连接。我们做删除操作时并不需要“剪断”整个节点只需要让前面一个环的 next 跳过当前环指向下一个环即可。关键来了在这道题中我们要让 cur 表示“当前正在检查的节点”。对于 cur.next我们可以决定“要不要保留它”。如果 cur.next 的值和 cur 的值相等我们就把 cur.next 指向 cur.next.next等于把 cur.next 这个节点从链表中摘掉。在这个过程中cur 本身根本没有变它的 val 也没有被替换变的只是它指向的下一个对象。这就是“通过 cur 调整后继指针”的思路。它天然适合本题因为我们只要保留每个重复组的第一个节点后续重复节点可以通过这个节点的 next 不断跳过。2.2 哨兵节点的价值做链表题目时我们常听到一个词dummy node也就是虚拟头节点也叫哨兵节点。它是在真正的头节点前面再额外设置一个节点让代码统一处理“删除头节点”和“删除中间节点”的情况。但在 LeetCode 83 这道题里头节点是永远不会被删除的。因为题目是“保留一个”而链表的第一个节点就算有重复值我们也会保留它作为该值的唯一代表。既然头节点不会被删我们就没必要引入 dummy node。直接用一个 cur 指向 head最后返回 head 就完事了。那为什么 LeetCode 82 必须用 dummy因为 82 要求删除所有重复节点当 1 - 1 - 2 时头节点 1 也要被删。如果不用 dummy你就得单独写一个“如果头节点重复就移动头节点”的逻辑很容易漏掉连续重复三次的情况。所以理解“什么时候需要哨兵”这件事比背模板更重要。3. 核心思路一次遍历边走边删3.1 最简单的迭代法边走边删我们直接用一个 cur 指针从头开始遍历。核心逻辑只有三步判断 cur.next 是否存在如果存在则检查它是否和 cur 的值相等。如果相等就把 cur.next 指向 cur.next.next相当于删掉了这个重复节点。注意此时不要移动 cur因为删掉一个之后新的 cur.next 可能还是重复值得继续检查。如果不相等就说明 cur 和下一个节点值不同此时让 cur cur.next移动到下一个节点上。这么说可能还有点抽象我们用 1 - 1 - 2 - 3 - 3 走一遍cur 指向第一个 1。看 cur.next 是第二个 1值相等于是把 cur.next 指向 2链表变为 1 - 2 - 3 - 3。cur 仍然在第一个 1 上再看 cur.next现在是 2不相等cur 移动到 2。cur 在 2cur.next 是 3不相等cur 移动到 3。cur 在第一个 3cur.next 是第二个 3相等把 cur.next 指向 null链表变为 1 - 2 - 3。cur 在 3cur.next 是 null循环结束。返回原来的 head也就是 1 - 2 - 3。整个过程里cur 从未被修改值它只是作为一个“探针”检查后继节点。为什么要这样设计因为当你想删除某个节点时必须让“它的前一个节点”的 next 指向它的下一个节点。在单向链表里前一个节点无法直接找到所以最容易的方式就是让 cur 充当“前一个节点”的角色用它来删除 cur.next。这个思路在做任何“删除当前节点的下一个节点”的操作时都通用。3.2 双指针写法快慢指针与变种除了单指针也有人喜欢用快慢指针。准备两个指针 prev 和 curprev 初始化为 headcur 初始化为 head.next。遍历时如果 cur 的值等于 prev 的值就让 prev.next cur.next同时 cur cur.next否则让 prev 先移到 cur再让 cur cur.next。这样写其实和单指针是同一个道理只是把“cur”和“cur.next”换成了“prev”和“cur”。它的好处在于当有人搞不清“删除后要不要移动指针”时双指针能更直观地看出 prev 是“已处理好的最后一个节点”cur 是“正在检查的节点”。但是面试时我不推荐写双指针版本因为 LeetCode 83 用单指针已经足够简洁双指针代码量更长且如果 prev 移动时机不对很容易出现重复节点保留过多的问题。双指针更适合后面要讲到的 LeetCode 82因为那种场景需要记录“重复段的前一个节点”。所以我的建议是先吃透单指针版本再拿双指针做对照练习而不是一上来就写复杂版本。4. 手把手代码实现Python / Java / C 三种语言4.1 Python 实现与代码解释def deleteDuplicates(self, head): 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 head让 cur 从头部开始。while cur and cur.next保证了循环过程中不会访问空引用。这里第一个cur条件主要是为了处理空链表如果 head 是 nullwhile 直接不执行返回 null。在循环内if cur.val cur.next.val是核心判断。当值相等时我们执行cur.next cur.next.next。这时 cur 不移动因为新的cur.next可能仍然和 cur 值相等。比如链表是 1 - 1 - 1第一次删除后变成 1 - 1如果马上让 cur 往后走就会漏掉第二个重复的 1。很多新手在这里踩坑根本原因就是“删完一个就放松警惕”。else分支里cur cur.next表示当前节点与下一个节点值不同所以当前节点已经安全可以移动到下一站。循环结束时所有重复节点都被跳过最后返回 head 即可。4.2 Java 实现与代码解释public ListNode deleteDuplicates(ListNode head) { ListNode cur head; while (cur ! null cur.next ! null) { if (cur.val cur.next.val) { cur.next cur.next.next; } else { cur cur.next; } } return head; }Java 和 Python 的逻辑完全一致。唯一要注意的是 Java 里要写cur ! null cur.next ! null而不是cur.next ! null cur ! null。这是短路求值的问题如果 cur 为 null 时先判断 cur.next就会抛出空指针异常。所以永远要把判空条件写在前面。这段代码对内存的影响在 Java 中是需要考虑的。被“跳过”的节点也就是原先是 cur.next现在被 cur.next.next 替代掉的那些节点不再有任何引用指向它JVM 的垃圾回收会自动回收。如果面试官追问“手动管理内存的语言怎么做”可以参考下面的 C 版本。4.3 C 实现与内存释放class Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode* cur head; while (cur ! nullptr cur-next ! nullptr) { if (cur-val cur-next-val) { ListNode* temp cur-next; cur-next cur-next-next; delete temp; } else { cur cur-next; } } return head; } };C 版本特意加了一行删除节点的操作。因为在 C 中链表节点如果是 new 出来的你不 delete 就会内存泄漏。这里用temp先保存要删除的cur-next然后让cur-next指向下下个节点最后delete temp。如果直接写成cur-next cur-next-next而不这行 delete程序也能跑出正确结果但在内存受限的面试场景或者严格的生产项目中这是不合格的。一个小细节是C 里同样要小心cur-next的重复访问。建议先把cur-next存下来既方便 delete也避免多级指针表达式让人看晕。4.4 复杂度分析时间复杂度是 O(n)其中 n 是链表长度。因为每个节点最多被访问一次。具体来说cur 不断向后移动即使重复节点被删除cur 仍停在原处继续检查新的后继但整体上所有节点都只会经历常数次比较。空间复杂度是 O(1)因为只定义了一个 cur 指针没有使用额外的数据结构。这一点也是面试官特别看重的链表的原地删除操作如果额外申请数组或哈希表就失去了链表操作的“优雅感”。有些人会误解“递归算不算 O(n) 空间”递归版本需要系统调用栈空间复杂度是 O(n)后面讲到递归时我们会细说。5. 常见问题与排查技巧实录5.1 为什么我的代码在删除节点时丢失了后续节点这是一个高频低级错误。有人写成这样while cur and cur.next: if cur.val cur.next.val: cur cur.next.next # 错误 else: cur cur.next这行在干嘛它把 cur 本身跳到了下下个节点而不是修改当前节点的 next 指向。如果链表是 1 - 1 - 2第一次循环时 cur 变成 2链表还是 1 - 1 - 2等于把 cur 的遍历位置跳过了第二个 1并直接跑到 2那么第二个 1 永远没被处理。最致命的是当重复节点连续多个时链表结构完全没有改变只是 cur 在四处乱窜最后返回 head 发现原链表根本没变。正确的做法是始终记住这一点删除节点时被改变的是前驱节点的 next而不是前驱节点本身。我们只做cur.next cur.next.nextcur 还是那个 cur只是它指向的目标变了。5.2 如何处理头节点本身就是重复值的情况很多同学遇到 1 - 1 - 2 会紧张担心头节点被删掉找不到入口。但实际上头节点作为重复组的第一个节点它是被保留的。我们从头开始看cur 指向第一个 1然后发现 cur.next 也是 1于是删掉 cur.next链表变成 1 - 2。整个过程 head 始终指向第一个 1一直没有变。最终返回 head 完全没问题。如果你用了哨兵节点就不能返回 head 了要返回 dummy.next。这是我见过最多的混淆点。有人明明没写哨兵却在最后返回dummy.next结果空指针有人写了哨兵却在最后返回 head结果把哨兵后面所有节点都丢了。解决办法就是动手前想清楚这个链表有没有引入额外的虚拟头有就返回 dummy.next没有就返回 head。5.3 循环条件应该写 cur ! null 还是 cur.next ! null这两种写法都不致命但直接关系到代码的简洁性与安全性。推荐写法是while (cur ! null cur.next ! null)。因为循环体内部访问了cur.next和cur.val如果不先保证 cur 非空空链表输入直接崩。如果只写while (cur.next ! null)当 head 为 null 时在循环条件判断阶段就会访问 null.next直接空指针。有人可能会说那我可以在 while 外面加一个if (head null) return head。这样当然也行但多一步不如少一步。写代码时把保护条件放进 while 里可以让函数对空输入天然健壮。5.4 空指针异常与“输出不变化”的调试方法我建议所有刷链表题的人都把打印节点值当成一种调试习惯。比如在循环里临时加一行打印观察每次比较的值和 cur 的移动过程while cur and cur.next: print(fcur{cur.val}, next{cur.next.val}) if cur.val cur.next.val: cur.next cur.next.next else: cur cur.next从打印结果你能直观看到cur 在每个非重复节点上停了一下在重复节点上连续执行删除操作而不移动。如果打印发现 cur 移动得太快或太慢基本就能定位到是“删后该不该移动”的问题还是“值比较反了”的问题。还有一个经典调试套路构造最小测试用例。不要一上来就测一万个节点先测1再测1 - 1再测1 - 1 - 2再测1 - 1 - 1 - 1。这些边界组合能覆盖大多数逻辑漏洞。我的实测经验是只要你在这四组样例上全过这道题代码基本就稳了。6. 变形与延伸从 LeetCode 83 到 LeetCode 82你能举一反三吗6.1 删除所有重复节点一个不留LeetCode 82LeetCode 82 是 LeetCode 83 的经典升级版要求删除所有重复的节点只保留出现一次的元素。比如 1 - 2 - 2 - 3要返回 1 - 3如果 1 - 1 - 2则返回 2。这个思路核心变化有两点。第一头节点可能被删除所以必须用 dummy 节点来统一操作。第二不能只比较 cur 和 cur.next 的值因为你不知道后面还有多少个重复值需要用一个循环把一整段重复值全部跳过。具体做法是如果 cur.next 和 cur.next.next 值相等就记下这个重复值然后不断让 cur.next cur.next.next 直到 cur.next 的值不等于这个重复值如果不相等cur 才往后移动。把这题和 83 放在一起对比能深刻体会“保留一个”和“完全删除”之间代码设计上的差异。83 是删除后 cur 不动等下一个后继出现82 是要一次性跳过整段重复节点。很多人在 82 上卡住就是因为还在用 83 的思维试图一个个删结果删到一半发现 cur 已经走到重复段的内部没法回头。6.2 递归解法与递归的代价LeetCode 83 还可以用递归实现def deleteDuplicates(self, head): if not head or not head.next: return head head.next self.deleteDuplicates(head.next) return head.next if head.val head.next.val else head这个递归版本虽然代码短但理解门槛略高。它的核心思想是先递归处理 head 之后的链表得到一个“已经删完重复的链表”然后比较 head 和当前 head.next 的值。如果相等说明 head 是一个重复值应该被舍弃所以返回 head.next否则 head 应该保留并且它的 next 指向已经处理好的链表。递归解法适合用来练习递归思维的入门题但在面试时不建议优先写。第一空间复杂度 O(n)如果链表特别长可能栈溢出。第二递归的返回规则容易让对方绕晕。除非面试官明确要求写递归否则迭代版本是更好的选择。6.3 如果链表没有排序会怎么样如果题目改成“未排序链表中的重复元素”那就没法用相邻比较来删除了。最常见的做法是借助哈希集合记录已经出现过的值。遍历一遍链表遇到没见过的值就加入集合遇到见过的值就删除。这样时间 O(n)空间 O(n)。这个变体可以用来理解“排序”这个前提对算法设计的影响。排序让问题退化为线性扫描不需要额外空间未排序就必须付出空间代价来记忆历史值。这也是为什么面试官喜欢围绕这道题出变形一场对话里能同时考察你对数据结构基础、空间复杂度、边界处理的理解。你甚至可以把这道题和“有序数组去重”对比着看。数组去重可以用双指针原地操作链表去重用 cur 单指针。两者都是 O(1) 空间的经典解法但数组的双指针是为了腾出前部位置链表的指针则是为了跳过节点。殊途同归但操作对象不同对思维的锻炼也不同。7. 写在最后的经验教训我个人在刷题和带人刷题的过程中发现链表类题目容易出错的根源往往不是语法不熟而是动手前没有明确“谁负责检查、谁负责删除、谁负责移动”。LeetCode 83 的答案虽然只有几行但值得你花一晚上去把它讲清楚。如果你能流畅地向别人解释清楚为什么删除后 cur 不移动为什么删除的是 cur.next 而不是 cur 本身为什么返回 head 而不是 cur那你就真的掌握了。最后分享一个小习惯每做一道链表题我都会把“是否使用哨兵节点”“返回哪个节点”“删除后是否移动指针”这三个问题写在题解旁边。等做到 LeetCode 82、86、206 这类更复杂的题时这些笔记会直接变成你的条件反射。链表题就像骑自行车路线可能千变万化但只要把“保持一个稳定前驱”这个基本功练好遇到新题目时心里就不会慌。