先说个我刷题时的真实感受很多人在LeetCode上遇到“83. 删除排序链表中的重复元素”这道题第一反应是“这不就是Easy题嘛”然后写个HashSet或者新建一个链表顺手就交了。等面试的时候被面试官追问一句“你能不用额外空间吗”或者让你现场把边界条件画一遍不少人就卡住了。这道题确实不难但它是检验链表基本功的一道好题——你是在机械地记忆代码还是真的理解了单链表的结构、指针语义和有序性带来的便利一测便知。下面我用实际做题的思路把这题从头到尾拆开讲透并把这套思路延伸到高频变体题和真实面试场景里。1. 为什么“有序”这两个字是这题的题眼先回到题目本身给定一个已排序的链表删除所有重复的元素让每个元素只出现一次。比如输入1 - 1 - 2输出1 - 2输入1 - 1 - 2 - 3 - 3输出1 - 2 - 3。如果只盯着“删除重复元素”这六个字很容易往“记录出现过的值”这个方向想。很多人的第一版解法就是弄一个哈希集合遍历链表如果当前值没出现过就保留出现过就跳过。这样做当然能通过时间复杂度O(n)空间复杂度却是O(n)。但这道题里有一个被低估的前提条件链表是排序好的。这意味着什么意味着所有重复的值在物理位置上一定是紧挨着的。既然重复项一定是连续的一段我们根本不需要记住之前见过哪些值只需要比较“当前节点”和“下一个节点”是否相等就够了。因为如果当前节点和下一个节点不相等那下一个节点和后面某些节点相等的可能性完全不影响当前节点——当前节点已经可以直接保留。这个“相邻比较”的思路让空间复杂度降到了O(1)。这也是面试官期待的答案利用数据有序性把哈希表的额外空间省掉。说实话算法题里很多优化都来自同一个套路——“别处理所有情况去处理你真正需要处理的情况”而有序性就是那个能让你“偷懒”的合法理由。2. 单链表里“删除”到底是什么指针操作的本质在写代码前我建议先把链表的物理结构在脑子里过一遍。链表不是数组它的节点在内存里是分散的每个节点只知道自己后面是谁。定义一个节点长这样public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }一个链表节点就两个信息当前的数值val以及指向下一个节点的引用next。在链表上做“删除”本质上不是把节点从内存里抹掉——在Java里我们也没有这个能力那是GC的事。删除的核心操作是改写引用让前一个节点的next指向被删节点的下一个节点。一旦没有任何引用指向被删节点它就会被垃圾回收机制自动清理。比如链表A - B - C要删除B只需要让A.next C。这里有个初学者很容易绕进去的误区删除节点时我们根本不关心被删除节点的next指向哪里也不需要显式释放内存。你只需要保证一个前提删除操作发生前必须持有被删节点的前一个节点。为什么呢因为单链表只能从前往后走。我在B这个位置我能拿到B.next但我拿不到B.prev——根本不知道是谁指向B。所以删除时必须用一个指针停留在B前面的A上通过修改A.next来“跳过”B。这就是这题迭代解法里cur指针为什么必须停留在重复段的前一个节点上的根本原因。很多同学看完答案能默写但把“让指针停在正确的位置”这个逻辑吃透的人不多。一旦你真正理解了它后面碰到任意链表删除题你都不会再怕。3. 迭代解法最容易写错的是“什么时候该移动cur”直接给代码然后再拆解里面的判断逻辑class Solution { 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; } }代码只有十行左右但你要注意一个细节当遇到重复时我让cur.next指向cur.next.next但是cur本身没有移动。这是这道题我最想强调的地方。假设链表是1 - 1 - 1 - 2。如果用cur cur.next来处理相等的情况第一轮cur在第一个1cur.next也是1相等处理完之后cur跑到第二个1第二轮cur在第二个1cur.next还是1相等处理完之后cur跑到第三个1第三轮cur在第三个1cur.next是2不相等继续移动。看起来好像也能跑不对你再仔细看第一轮处理完之后链表结构会变但如果你同时把cur往前移动就会滑过新暴露出来的重复节点。正确做法是当发现当前节点和下一个节点值相等时只修改cur.next的指向把下一个节点“跨过去”然后停在原地继续比较当前节点和新的下一个节点。因为旧的cur.next被替换了新的cur.next仍然可能是相同值。处理完重复后cur指向的节点的下一个节点才是不同的值此时cur cur.next才能安全地前进。再看一下边界情况空链表head nullwhile条件直接不满足返回null没问题。只有一个节点cur.next null循环退出返回原节点没问题。结尾连续重复比如1 - 2 - 2 - 2。cur在2时发现和cur.next相等就不断执行cur.next cur.next.next直到cur.next为null或值不同。循环结束时cur仍然指向第一个2但后续重复项已经被跨过了。用Python写逻辑完全一样class Solution: def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]: cur head while cur and cur.next: if cur.val cur.next.val: cur.next cur.next.next else: cur cur.next return head提示这段代码里有一个隐含假设——head本身的值不会被改变所以最后直接返回head。如果这道题要求“只要重复就一个不留”那个场景下头节点可能被删就必须用dummy node了。这点我在第5章会细说。复杂度方面每个节点最多被访问一次时间复杂度O(n)没有使用哈希表空间复杂度O(1)。这也是解法中最优的时空表现。4. 递归解法用“递”的视角看这个问题的分层结构除了迭代还可以用递归写。递归解法的存在意义不完全在于效率而是帮助我们从另一个角度理解链表的结构——链表本质上是一种递归定义的数据结构一个节点后面跟着另一个链表。递归的思路是这样的我处理当前节点时先别管后面的重复情况我只确保两个东西如果当前节点和下一个节点值相同我就“跳过”当前节点直接返回“对下一个节点递归处理”的结果。如果当前节点和下一个节点值不同我就保留当前节点当前节点的next指向“对后面链表递归处理”的结果。代码长这样class Solution { public ListNode deleteDuplicates(ListNode head) { if (head null || head.next null) { return head; } head.next deleteDuplicates(head.next); if (head.val head.next.val) { return head.next; } else { return head; } } }走一遍1 - 1 - 2最外层递归head在第一个1先递归处理后面的1 - 2第二层递归head在第二个1先递归处理后面的2第三层递归head在22.next为null返回2回到第二层head.next等于第三层的返回值2比较第二个1.val和2.val不相等返回第二个1所以第二层返回的是1 - 2回到第一层head.next等于第二层的返回值1 - 2比较第一个1.val和1.val相等返回head.next也就是1 - 2。整个过程中每一层只负责“当前节点和子链表头节点”的关系重复节点就像一个一个被“剥掉”的洋葱皮。递归的终止条件是当前节点为null或只有一个节点——这是递归题的通用底线。递归解法的空间复杂度是O(n)因为递归调用栈要存每一层的信息。在链表非常长几万个节点时理论上可能触发栈溢出所以生产级代码里迭代解法更稳妥。但递归版本在面试里可以作为补充答案展示思路面试官很吃这一套——能讲清楚递归调用栈的进出过程说明你真的理解了链表的递归本质。5. 一个极容易被忽略的问题为什么这题不需要dummy node刷题多的人对dummy node虚拟头节点一定不陌生它长这样ListNode dummy new ListNode(-1); dummy.next head;,在需要删除头节点的题目里dummy是必杀技。但这道题很多答案都没有用dummy原因是这题的头节点永远不会被删除。为什么因为题目要求的是“保留一个”。如果一个值出现了多次我们保留的是这组重复值中的第一个而头节点恰好就是第一组重复值的第一个。无论后面的节点怎么删头节点始终被保留。所以最后可以理直气壮地return head。但如果你做的是变体题LeetCode 82“删除排序链表中的重复元素II”要求“只要元素出现重复就全部删除一个不留”情况就不一样了如果整个链表是1 - 1 - 2 - 3头节点1是重复的必须被删掉。这时候head本身可能被删除你就必须引入dummy node来占住位置最后返回dummy.next。这个对比本身就是一道很好的面试追问。面试官常常会用这种“同场景不同要求”的方式来考察你你不是背了两道题吗那请你讲讲这两道题用不用dummy的本质区别是什么。区别就一句话当且仅当链表的头节点有可能被删除时才需要dummy node。这是一个在链表题里放之四海而皆准的判断标准。6. 从这题延伸开去变体题和面试追问的应对思路这道题在面试中经常自带“加餐题目”刷题不用只盯着83题本身最好把下面这些变体一起搞清楚。6.1 LeetCode 82重复元素一个不留核心代码逻辑和83题不同不能简单地“保留一个”而是要把一整段重复值全部跨过去class Solution { public ListNode deleteDuplicates(ListNode head) { if (head null) return head; ListNode dummy new ListNode(-1, head); ListNode cur dummy; while (cur.next ! null cur.next.next ! null) { if (cur.next.val cur.next.next.val) { int val cur.next.val; while (cur.next ! null cur.next.val val) { cur.next cur.next.next; } } else { cur cur.next; } } return dummy.next; } }这个解法里有两个关键点一是用dummy兜底因为头节点可能被当成重复元素删掉二是用while而不是if来处理整段重复。当发现cur.next.val cur.next.next.val时先把重复值记下来然后不停地把cur.next往后移直到下一个节点的值不再等于这个重复值。注意这里cur本身没有动因为跨过一整段重复之后新的cur.next可能又和后面的节点重复了需要继续处理。6.2 类似思路的上手迁移把 “83题 82题” 这一对题目吃透很多链表操作题都能触类旁通LintCode / LeetCode 26题“删除有序数组中的重复项”虽然数据结构变成了数组但核心思想一模一样。数组版本更简单因为可以通过“覆盖”来删除元素不需要改指针。用快慢指针时慢指针指向新数组的尾部快指针负责向后探索发现新值就搬到前面来。对比链表和数组两种实现能更加理解“有序”这个概念在两种数据结构里的不同表达方式。LeetCode 203“移除链表元素”删除所有值等于给定值的节点。因为头节点可能被删也需要dummy node。在写法上它跟82题很像但判断条件从cur.next.val cur.next.next.val变成了cur.next.val val本质上都是“检查后继节点是否满足删除条件”。LeetCode 21“合并两个有序链表”合并过程涉及大量next修改操作。写完83题再写21题你会自然形成一种“指针只能在链表上单向移动”的直觉这对理解链表合并过程非常有帮助。6.3 如果面试官追问“链表没有排序怎么办”这也是一道经典追问。如果链表是有序的重复元素必然相邻可以O(1)空间去重但如果链表无序相邻元素并不能代表是否重复过必须用哈希表记录已经出现的值。此时哈希集合是必不可少的因为不知道当前节点之前有没有出现过同值节点。解法是保存一个prev指针前一个节点和一个HashSetInteger seenclass Solution { public ListNode deleteDuplicatesUnsorted(ListNode head) { SetInteger seen new HashSet(); ListNode dummy new ListNode(-1, head); ListNode cur dummy; while (cur.next ! null) { if (seen.contains(cur.next.val)) { cur.next cur.next.next; } else { seen.add(cur.next.val); cur cur.next; } } return dummy.next; } }注意这里仍然用了dummy node因为无序链表的头节点也可能因为“之前见过相同值”而被删除。这一题的出现恰好反过来印证了排序条件为83题带来的优化空间。6.4 相关变体对比表题目要求是否有序是否需要额外空间是否用dummy node核心操作83题保留一个有序否否相邻比较跳过重复节点83题无序版保留一个无序是哈希集合是哈希集合记录已出现值82题一个不留有序否是用while跨过整个重复段删除指定值节点不一定否是检查后继节点是否为指定值有序数组去重有序否不适用快慢指针覆盖写入这张表值得收藏。面试前花三十分钟把这几道题一起过一遍效果远大于孤立地刷十道题。7. 手写这道题时最容易翻车的四个细节这题虽然代码短但我在实际带新人和模拟面试时见过太多人在以下四个细节上翻车。专门列出来提醒一下。细节一漏掉cur ! null判断就直接访问cur.next。空链表是合法的输入之一没有判空直接写while (cur.next ! null)空链表直接空指针异常。正确做法是while (cur ! null cur.next ! null)短路求值会保证cur.next安全访问。细节二相等时用if而不是while处理连续重复。有人在Java代码里写的是if (cur.val cur.next.val) { cur.next cur.next.next; cur cur.next; }这段代码在1 - 1 - 1这样的用例上会出错。虽然题目给的是“已排序”但重复可能连续出现三次甚至更多次。使用if只能跨过一个重复节点所以必须用while持续判断只要当前节点和新的下一个节点还相等就继续跨直到不同为止。很多同学在自己IDE里跑通1-1-2就觉得万事大吉忽略了1-1-1-2这种用例。细节三搞混“节点相等”和“值相等”。题目要求删除的是“重复的元素”即val相同的节点。但链表里的节点对象本身是不同的。对ListNode对象使用在Java中比较的是引用地址不是值。判断重复时一定要用cur.val cur.next.val而不是cur cur.next。这个错误在刷题初期特别容易被Python用户忽略——Python里如果你没用val属性比较直接拿节点对象比较结果永远是False因为Python自动调用的__eq__本质上是内存地址比较。细节四忽略了返回值的正确性。迭代版本里有些人习惯用cur作为返回值这是典型的错误。当遍历结束时cur已经走到了链表尾部返回它就等于返回最后一个节点。正确应该是返回原链表的头节点head。一看到“删除”就觉得要新建链表来存储结果的思维是链表题最大的绊脚石——原地修改指针头节点不变就是你想要的结果。8. 选用迭代解法为主、递归解法为辅的工程考量很多刷题文章喜欢把两种解法并列说明思路就完了。但结合实际工程习惯我想说说我个人的取舍。日常开发里如果拿一段业务代码让我分析链表操作优先选择迭代解法。原因不是递归不好而是链表的递归思路虽然优美但存在几个实际工程问题一是递归调用栈会占用额外空间在链表数据量较大时可能栈溢出二是代码可读性看似简洁但如果维护的人不熟悉递归理解成本很高三是递归版本的调试体验比较痛苦——单步调试时要一层一层跳来跳去远不如迭代版本一顺到底来得好理解。递归解法更适合什么场景第一链表本身就是递归定义的数据结构某些问题用递归描述会特别清晰比如反转链表、合并两个有序链表第二面试时用来展示对不同解法的理解深度第三当链表长度可控、数据量不大时递归在代码简洁度上胜出。我自己的习惯是“面试先讲递归思路建立直觉再给迭代解法作为最终实现并解释两者时空复杂度的差异”这样既能体现思维层次又展现工程务实的一面。工程上还有一个值得说的点是处理这类链表问题时尽量不创建新的链表节点而是在原链表上修改指针。表面上看新建一个链表也能通过题目但它会在面试中被扣分——因为题目考察的就是原地修改和指针操作能力新建链表相当于绕开了考点也让空间复杂度不再是O(1)。除非题目明确允许复制节点否则默认都优先原地操作。9. 从这道题带出的个人刷题心得最后聊点关于刷题节奏的东西。LeetCode有三千多道题如果无差别地刷很快就会进入“题目做了、思路忘了”的循环。我现在带人刷题特别强调“同类题打包刷”。像83题这样看似基础的题目它的价值不在于题目本身有多难而在于它能够连接到多少个变体和面试追问。把83题、82题、21题、206题反转链表放在同一周内练习你会发现它们之间的共性——都是在玩“前后节点指针关系”这个游戏。我自己的练习方法是这样的拿到一道链表题先不急着写代码拿出一张纸把链表画出来手动模拟删除节点的过程。思考顺序是“谁指向谁改谁的next最终返回谁”。把这三句话想清楚再落代码准确率会高非常多。83题我第一次刷的时候也踩了“相等时cur也向后移动”的坑后来认真画图模拟1 - 1 - 1 - 2的执行过程才真正理解为什么相等的分支不能移动cur。这道题讲完你会发现它虽然只有十行代码但背后的“有序性利用”“指针操作原理”“递归分层思路”“变体迁移方法”一整套东西对于链表类题目的入门来说太值得吃透了。碰到一个看似简单的题别急着跳过多问自己一句“如果去掉某个条件解法会怎么变化”这道题才算真正刷透了。