教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是《算法通关手册》AlgoNote 题解的深度解析。文章以该题解为骨架结合仓库中单链表的底层实现与链表基础教程讲解利用有序性 单指针遍历原地去重这一核心技巧并对照保留一个副本0083与全部删除重复项0082两种删除语义帮助读者掌握链表指针操作的边界处理。读完本文你将能独立写出可运行的 O(n) 时间、O(1) 空间的链表去重代码并理解它与有序数组双指针去重的联系与差异。1. 题目回顾题目描述给定一个已排序链表的头节点head删除其中所有重复的元素使每个元素只出现一次并返回已排序的链表。题目说明链表中节点数目在范围[0, 300]内-100 Node.val 100题目数据保证链表已经按升序排列。示例输入head [1,1,2,3,3] 输出[1,2,3]该题对应 LeetCode 0083标签为「链表」难度为「简单」被收录在《算法通关手册》的 00_05 题解列表 与 00_06 分类列表 的链表基础分类中也出现在 00_07 面试 100 题列表 和 00_08 面试 200 题列表 中属于面试高频题。2. 核心思想利用有序性 单指针遍历解决这道题的关键前提是链表已经按升序排列。这意味着所有值相同的节点在链表中必然连续出现例如[1,1,2,3,3]中的两个1相邻、两个3相邻。因此我们不需要借助哈希表或额外数组统计频次只需在遍历过程中比较当前节点与下一个节点的值是否相等相等就跳过下一个节点即可完成原地去重。这与仓库中链表基础教程对链表的定位一致链表是链式存储的线性表节点间通过next指针串联只能顺序访问、不支持随机访问参见 链表基本概念与操作 第 3.4 节链表 vs 数组。这种顺序访问的特性恰好适合本题——去重过程本身就需要顺序遍历天然契合链表结构。3. 思路 1遍历解法标准答案3.1 算法步骤使用指针curr遍历链表先将头节点head保存到curr循环判断curr.next是否存在同时比较当前元素的值与下一个节点元素的值如果相等说明出现重复则让curr.next指向下下个节点即跳过重复节点如果不相等则让curr继续向后移动一个节点遍历完成后返回头节点head。这里有一个容易混淆的细节当检测到重复并执行curr.next curr.next.next后curr本身并不移动而是继续留在原地与新的下一个节点比较。例如链表[1,1,1,2]第一次比较发现两个1重复跳过第二个1后curr仍指向第一个1此时再次比较curr.val与新的curr.next.val发现还是1与1重复于是继续跳过——这正是循环连续去除多个重复节点的关键。只有当当前节点与下一个节点值不同时curr才前进。3.2 参考代码# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def deleteDuplicates(self, head: ListNode) - ListNode: if head None: return head curr head while curr.next: if curr.val curr.next.val: curr.next curr.next.next else: curr curr.next return head3.3 复杂度分析时间复杂度O(n)其中 n 为链表长度。整个遍历过程中每个节点最多被访问常数次空间复杂度O(1)。只使用了常数个指针变量不申请额外存储空间。4. 边界情况与易错点分析本题虽然思路简单但边界处理是面试考察重点需要逐一确认空链表head None代码开头直接返回head即None避免进入while curr.next时访问空指针只有一个节点的链表curr.next为None循环条件不成立直接返回head无需任何处理头节点就是重复节点本题不需要删除头节点本身重复值保留一个因此无需哑节点dummy node返回head依然正确。这一点与重复项全部删除的 0082 题 不同0082 因为可能删掉头节点才必须借助哑节点多个连续重复节点如[1,1,1,1]依赖上文所述的跳过时不移动curr逻辑逐个跳完最终只剩一个值为1的节点。5. 仓库源码佐证链表节点与指针操作本题的指针操作建立在对链表结构的基本认知之上。仓库中 链表基础教程 定义了最基础的节点结构# 链节点类 class ListNode: def __init__(self, val0, nextNone): self.val val # 节点的值 self.next next # 指向下一个节点在 codes/python/02_linked_list/linked_list.py 中可以找到本题所用指针操作的直接对应实现。例如「删除元素」操作的核心语句见removeInsidedel_node cur.next # del_node 指向待删除的节点 cur.next del_node.next # 将 cur 的 next 指针指向 del_node 的下一个节点实现删除本题中的curr.next curr.next.next本质上就是这条语句的简化写法把当前节点的后继指向后继的后继从而在链表中摘除中间节点。区别仅在于去重场景不需要单独保留被删除节点的引用Python 会自动回收不再被引用的节点。另外「求链表长度」与「查找节点」等操作在 linked_list.py 中同样采用while cur:/while cur.next:形式的遍历说明本题的遍历终止条件写法与仓库一致属于仓库代码规范中的常规模式。6. 变式对比保留一个副本 vs 全部删除重复项6.1 0082删除所有重复数字只保留唯一元素与本题相邻的 0082. 删除排序链表中的重复元素 II 要求把所有重复出现的数字全部删掉一个都不留。其解题思路与本体的差异点在于构造哑节点dummy_head指向head防止从head开始就是重复元素而无法删除用指针cur遍历当cur.next与cur.next.next都存在时比较二者值值相同用临时指针temp向后跳过所有连续重复节点令cur.next temp.next一次删除一整段重复值不同cur右移一位遍历结束返回dummy_head.next。参考代码class Solution: def deleteDuplicates(self, head: ListNode) - ListNode: dummy_head ListNode(-1) dummy_head.next head cur dummy_head while cur.next and cur.next.next: if cur.next.val cur.next.next.val: temp cur.next while temp and temp.next and temp.val temp.next.val: temp temp.next cur.next temp.next else: cur cur.next return dummy_head.next两者对比可归纳如下对比维度0083本文0082变式删除语义重复值保留一个重复值全部删除是否删除头节点否重复值仍保留可能如[1,1,2]是否需要哑节点不需要需要防止头节点被删重复段处理逐个跳过用temp整段跳过标签/难度链表 / 简单链表、双指针 / 中等6.2 0026有序数组去重的双指针版本同类题目的数组版本是 0026. 删除有序数组中的重复项要求原地修改数组并返回新长度使用快慢指针class Solution: def removeDuplicates(self, nums: List[int]) - int: if len(nums) 1: return len(nums) slow, fast 0, 1 while (fast len(nums)): if nums[slow] ! nums[fast]: slow 1 nums[slow] nums[fast] fast 1 return slow 1对照理解更有价值数组无法物理断开元素只能用slow慢指针维护去重后有效区间的末尾把不重复元素依次前移覆盖最后返回长度链表支持 O(1) 的指针摘除操作已知位置时不需要慢指针维护有效区间只需curr单指针配合curr.next跳指针即可完成删除。两种结构共享同一个核心洞察有序序列中重复元素必相邻因此一次遍历即可完成去重时间复杂度均为 O(n)、空间复杂度均为 O(1)。7. 小结0083「删除排序链表中的重复元素」是链表基础题中的高频面试题其价值在于训练三个能力利用有序性简化问题——重复元素必相邻无需额外容器指针跳接删除节点——curr.next curr.next.next删除后原地不动的细节处理边界意识——空链表、单节点链表、连续多个重复节点等场景的正确处理。建议读者结合仓库中的 链表基础教程、链表类实现 以及 链表基础题目分类列表 中列出的反转链表、移除链表元素等题目进行系统练习将本题的指针操作内化为链表类题目的通用基本功。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐algorithm-base 链表篇LeetCode 82 删除排序链表中的重复元素 II —— 双指针侦察兵解法全解algorithm base 链表篇LeetCode 82 删除排序链表中的重复元素 II —— 双指针侦察兵解法全解 本篇是 algorithm base文档教程知识库LeetCode 83删除排序链表中的重复元素 Remove Duplicates from Sorted ListGo 题解LeetCode 83删除排序链表中的重复元素 Remove Duplicates from Sorted ListGo 题解 本文围绕 LeetCode示例工程0082 删除排序链表中的重复元素 IIAlgoNote 哑节点遍历解法全解析0082 删除排序链表中的重复元素 IIAlgoNote 哑节点遍历解法全解析 本文基于「算法通关手册」AlgoNote仓库中 删除排序链表中的重复元素教程文档知识库上一篇AutoUnipus3分钟完成U校园网课答题的终极Python脚本指南下一篇SysML v2革命如何用新一代建模语言破解复杂系统设计难题创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考