有序链表中删重复节点递归与三种迭代指针法详解leetcode1/leetcode 仓库 · LeetCode 83【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇围绕 leetcode1/leetcode 仓库中 remove-duplicates-from-sorted-list.md 这篇解题文档展开完整讲解 LeetCode 83「Remove Duplicates from Sorted List」的三种解法——递归、内层循环迭代、单循环分支迭代——并对照仓库里 python、java、cpp、go、c 五个语言目录下的真实提交分析同一问题的指针设计差异帮助你在“就地删除重复节点”这一链表核心操作上形成系统化的判断能力。1. 问题设定与前置知识问题描述给定一个排序升序的单链表要求删除所有重复的节点使每个元素只出现一次并返回处理后的链表。例如题目经典样例输入[1, 1, 2]→ 输出[1, 2]输入[1, 1, 2, 2]→ 输出[1, 2]这道题的价值不在“去重”本身而在于它迫使你掌握链表的就地in-place修改没有额外的数组副本可写只能通过重接next指针把重复节点从链中摘除。文档 Prerequisites 部分列出了动手前应掌握的三个前置能力这里逐条展开链表基本功理解节点结构、遍历方式和指针操作。本题所有解法都只依赖两个字段——val和next递归方法一从链表尾部向头部回溯式地处理需要理解“先处理后半段、再接管前半段”的递归返回语义有序结构的利用因为链表已排序重复值必然相邻所以只需比较相邻节点即可完成去重无需哈希表等额外结构。下文代码中统一使用的节点定义为 Python 的ListNode# Definition for singly-linked list. class ListNode: def __init__(self, val0, nextNone): self.val val self.next next其他语言的等价定义在文档中均有注释给出Java/C 的valnextKotlin/Swift 的可选值变体Rust 的OptionBoxListNode。2. 方法一递归——从表尾倒序清除重复2.1 直觉递归方案的思路是从链表末尾向前解决先把head.next开始的子链表递归地清理好再检查当前节点是否与已经清理过的后继节点值相同。若相同就把当前节点“跳过”——直接返回head.next让上一层的指针接管若不同则返回head。由于每一层递归都只保留每个值的一个代表节点长重复链如 1→1→1→1→2会被逐层自然剥掉不需要额外的计数或跳过逻辑。2.2 算法步骤基本情况链表为空或只有一个节点时直接返回递归清理以head.next开头的子链表用清理后的结果更新head.next若head.val head.next.val返回head.next跳过当前节点否则返回head保留当前节点。2.3 代码实现Pythonclass Solution: def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]: if not head or not head.next: return head head.next self.deleteDuplicates(head.next) return head if head.val ! head.next.val else head.nextJavapublic class Solution { public ListNode deleteDuplicates(ListNode head) { if (head null || head.next null) return head; head.next deleteDuplicates(head.next); return head.val ! head.next.val ? head : head.next; } }Cclass Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (!head || !head-next) return head; head-next deleteDuplicates(head-next); return head-val ! head-next-val ? head : head-next; } };JavaScriptclass Solution { deleteDuplicates(head) { if (!head || !head.next) return head; head.next this.deleteDuplicates(head.next); return head.val ! head.next.val ? head : head.next; } }Gofunc deleteDuplicates(head *ListNode) *ListNode { if head nil || head.Next nil { return head } head.Next deleteDuplicates(head.Next) if head.Val ! head.Next.Val { return head } return head.Next }Rust所有权模型下用OptionBoxListNode表达impl Solution { pub fn delete_duplicates(head: OptionBoxListNode) - OptionBoxListNode { match head { None None, Some(mut node) { node.next Self::delete_duplicates(node.next); if node.next.is_some() node.val node.next.as_ref().unwrap().val { node.next } else { Some(node) } } } } }C#、Kotlin、Swift 变体与上述逻辑一一对应区别只在空值处理语法如 Kotlin 的head?.next、Swift 的guard let、C# 的 null文档中均给出了完整代码可查阅 原文档。2.4 递归处理重复链的过程以1 → 1 → 2为例自底向上还原递归到达2单节点直接返回2回到第二个1它的next即2值不同保留自己返回1 → 2回到第一个1head.next更新为1 → 2而head.val head.next.val1 1于是不保留自己直接返回head.next即1 → 2。注意第 3 步被跳过的节点并没有被free/显式释放它只是脱离了引用链最终由语言的垃圾回收或内存管理器处理。如果重复链更长如1 → 1 → 1 → 2每一层递归都会重复这一步链越长“剥落”的层数越多但总层数仍不超过节点数。2.5 复杂度时间复杂度O(n)每个节点恰好被访问一次空间复杂度O(n)来自递归调用栈。这是方法一的实际代价——链表很长时栈深度等于节点数极端长度下有栈溢出风险。面试或生产环境中通常优先选择下面的迭代方案。3. 方法二迭代 I——内层循环整链跳过3.1 直觉链表有序意味着重复值连续。维护一个指针cur停在“当前保留值”的节点上用内层循环把后面所有值相同的节点一次性从链中摘除每删一个就让cur.next前移一格直到cur.next的值与cur不同或到达链尾。这样一条重复链只需一次外层推进就能清干净。3.2 算法步骤cur从表头开始当cur非空时检查后继节点是否同值若同值通过cur.next cur.next.next跳过后继节点持续跳过直到后继节点异值或为空将cur推进到cur.next重复上述过程返回head。3.3 代码实现Pythonclass Solution: def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]: cur head while cur: while cur.next and cur.next.val cur.val: cur.next cur.next.next cur cur.next return headJavapublic class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode cur head; while (cur ! null) { while (cur.next ! null cur.next.val cur.val) { cur.next cur.next.next; } cur cur.next; } return head; } }Cclass Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode* cur head; while (cur) { while (cur-next cur-next-val cur-val) { cur-next cur-next-next; } cur cur-next; } return head; } };JavaScriptclass Solution { deleteDuplicates(head) { let cur head; while (cur) { while (cur.next cur.next.val cur.val) { cur.next cur.next.next; } cur cur.next; } return head; } }Gofunc deleteDuplicates(head *ListNode) *ListNode { cur : head for cur ! nil { for cur.Next ! nil cur.Next.Val cur.Val { cur.Next cur.Next.Next } cur cur.Next } return head }3.4 关键点删除时不推进cur内层循环的精髓在于删节点时只改cur.next绝不移动cur本身。因为被摘除节点的“接替者”可能是另一个同值节点必须留在原地继续比对。只有当cur.next异值或为空时才允许cur cur.next前进。文档 Common Pitfalls 一节将这一点列为最常见的错误详见第 5 节。3.5 复杂度时间复杂度O(n)每个节点要么被跳过、要么被前进越过总操作量为线性空间复杂度O(1)额外空间只用了cur一个指针。这个版本与仓库中 python/0083-remove-duplicates-from-sorted-list.py 和 c/0083-remove-duplicates-from-sorted-list.c 的实现完全同构说明“双循环跳过”是该仓库提交中最主流的风格。4. 方法三迭代 II——单循环 条件分支4.1 直觉方法三把方法二的嵌套结构“拍平”只用一个while循环每一轮做一个二选一判断——若cur与cur.next同值就跳过cur.next否则推进cur。控制流更线性读起来更接近“伪代码”适合初学链表操作的人理解“删除节点 改指针不是删内存”这件事。4.2 算法步骤cur从表头开始当cur与cur.next都非空时若两者值相同更新cur.next跳过后继否则cur前进到后继节点返回head。4.3 代码实现Pythonclass 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 headJavapublic class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode cur head; while (cur ! null cur.next ! null) { if (cur.next.val cur.val) { cur.next cur.next.next; } else { cur cur.next; } } return head; } }Cclass Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode* cur head; while (cur cur-next) { if (cur-next-val cur-val) { cur-next cur-next-next; } else { cur cur-next; } } return head; } };JavaScriptclass Solution { deleteDuplicates(head) { let cur head; while (cur cur.next) { if (cur.next.val cur.val) { cur.next cur.next.next; } else { cur cur.next; } } return head; } }Gofunc deleteDuplicates(head *ListNode) *ListNode { cur : head for cur ! nil cur.Next ! nil { if cur.Next.Val cur.Val { cur.Next cur.Next.Next } else { cur cur.Next } } return head }4.4 与方法二的差异两者时间空间复杂度相同差别纯粹在控制流组织方法二把“连续同值”封装进内层while方法三把它展开为外层if/else的自转同值时cur原地不动循环自然再比对一次新后继。方法三在 Kotlin、Swift 等语言里因可选值判空语法略显啰嗦而方法二借助“先判空再取值”的结构反而更紧凑——文档为每种语言分别给出了两种写法可按语言特性择优。5. 常见陷阱文档 Common Pitfalls 一节总结了两个高频错误这里结合代码展开。5.1 指针推进时机错误删除重复节点后只应更新cur.next不能同时推进cur。设想1 → 1 → 1 → 2若在某一层把cur也向前挪了新暴露出来的后继仍是1就再也不会与cur比较残留的重复节点会漏删。正确纪律是值相同 → 改cur.nextcur原地不动值不同 →cur cur.next。这正是方法三if/else分支存在的意义也是方法二把“推进”写在内层循环之外、而不是循环体内的原因。5.2 空指针防护访问cur.next.val前必须先确认cur.next非空否则在链尾节点或空链表上会触发空指针异常C/C 的段错误、Java 的NullPointerException、JS 的Cannot read properties of null。安全的循环条件有两种等价写法while (cur and cur.next)方法三采用把判空收敛进循环条件内层while (cur.next and ...)方法二采用取值前先短路求值。另外要区分两种空语义head null空链表和head.next null单节点都应作为“无事可做”直接返回这也是递归解法第一行判空的原因。6. 仓库源码对照五种提交、四种指针风格leetcode1/leetcode 仓库在多个语言目录下收录了本题的真实提交完成状态可参考 README.md 中 0083 一行的勾选表它们的指针设计恰好覆盖了本题的典型风格谱系值得逐一对照文件实现风格指针设计复杂度python/0083-remove-duplicates-from-sorted-list.py迭代 I单指针cur 内层循环O(n) / O(1)c/0083-remove-duplicates-from-sorted-list.c迭代 I单指针cur 内层循环与 Python 版逐行同构O(n) / O(1)cpp/0083-remove-duplicates-from-sorted-list.cpp快慢双指针slow停在保留值上fast先扫描越过整段同值区再一次性接上slow-next fastO(n) / O(1)java/0083-remove-duplicates-from-sorted-list.java三指针 p/q/rq为当前保留节点r为探查节点p为上一节点注释自述“three pointer approach”O(n) / O(1)go/0083-remove-duplicates-from-sorted-list.goprev/curr 双指针prev保留、curr探查同值时推进curr并同步prev.NextO(n) / O(1)从源码结构看这些实现虽然指针命名各异但本质都是文档“迭代 I/II”两个骨架的变形C 版的快慢指针与文档迭代 I 等价只是把“内层循环逐个跳过”改写成“fast先整段扫过、再重接一次”在长重复链上少做一些中间赋值Java 版的 p/q/r引入了一个冗余的p上一节点——对于“保留每个值一个节点”的 83 题而言p并没有被使用到它只在需要“整段删除”的 82 题里才有意义这提示我们读社区提交时要分辨哪些状态是该题目真正必需的Go 版的prev, curr curr, curr.Next元组赋值体现了 Go 惯用法逻辑上仍与文档迭代 II 的单循环分支一一对应。这种“同一问题、多种指针编排”的对照正是把本文三种解法练熟之后能获得的额外收益你能快速看懂任意一种指针风格并心算其正确性。7. 三种解法对比与选型建议解法时间额外空间结构特点适用场景递归O(n)O(n)调用栈自底向上代码最短面试白板展示递归思维、节点数可接受的场景迭代 I嵌套循环O(n)O(1)“保留节点 内层清除”语义直白默认首选绝大多数语言的推荐写法迭代 II单循环分支O(n)O(1)控制流线性无嵌套教学讲解、避免嵌套循环可读性的场景选型要点生产代码优先迭代。递归版虽然最优雅但 O(n) 栈深度在数万节点量级就可能逼近语言栈限制迭代版没有这一隐患无论哪种解法删除动作永远只有“重接next”一种。不存在“删除节点”的原语理解这一点就理解了本题的全部难点边界三件套必须覆盖空链表、单节点、全同值链表如1 → 1 → 1最终只剩一个1。文档中三种解法的第一行判空与循环条件天然处理了前两者全同值链由内层循环/分支循环消化。最后提醒一个易混淆的延伸如果题目要求“重复值一个都不保留”即 LeetCode 82 的 Remove Duplicates from Sorted List II本文三种“保留首个”的解法都不适用需要引入prev指针在发现重复段后整段跳过——本文解法与它的边界区别也是面试追问的高频点。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
