企业官网建设流程全解析

• 教程
• 文档
• 知识库

本文是《算法通关手册》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 算法步骤

1. 使用指针curr遍历链表，先将头节点head保存到curr；
2. 循环判断curr.next是否存在，同时比较当前元素的值与下一个节点元素的值：
   • 如果相等（说明出现重复），则让curr.next指向下下个节点，即跳过重复节点；
   • 如果不相等，则让curr继续向后移动一个节点；
3. 遍历完成后，返回头节点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, val=0, next=None): # 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 head

3.3 复杂度分析

• 时间复杂度：O(n)，其中 n 为链表长度。整个遍历过程中每个节点最多被访问常数次；
• 空间复杂度：O(1)。只使用了常数个指针变量，不申请额外存储空间。

4. 边界情况与易错点分析

本题虽然思路简单，但边界处理是面试考察重点，需要逐一确认：

1. 空链表（head == None）：代码开头直接返回head（即None），避免进入while curr.next时访问空指针；
2. 只有一个节点的链表：curr.next为None，循环条件不成立，直接返回head，无需任何处理；
3. 头节点就是重复节点：本题不需要删除头节点本身（重复值保留一个），因此无需哑节点（dummy node）；返回head依然正确。这一点与"重复项全部删除"的 0082 题 不同，0082 因为可能删掉头节点，才必须借助哑节点；
4. 多个连续重复节点：如[1,1,1,1]，依赖上文所述的"跳过时不移动curr"逻辑逐个跳完，最终只剩一个值为1的节点。

5. 仓库源码佐证：链表节点与指针操作

本题的指针操作建立在对链表结构的基本认知之上。仓库中 链表基础教程 定义了最基础的节点结构：

# 链节点类 class ListNode: def __init__(self, val=0, next=None): self.val = val # 节点的值 self.next = next # 指向下一个节点

在 codes/python/02_linked_list/linked_list.py 中，可以找到本题所用指针操作的直接对应实现。例如「删除元素」操作的核心语句（见removeInside）：

del_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 要求把所有重复出现的数字全部删掉（一个都不留）。其解题思路与本体的差异点在于：

1. 构造哑节点dummy_head指向head，防止从head开始就是重复元素而无法删除；
2. 用指针cur遍历，当cur.next与cur.next.next都存在时，比较二者值：
   • 值相同：用临时指针temp向后跳过所有连续重复节点，令cur.next = temp.next，一次删除一整段重复；
   • 值不同：cur右移一位；
3. 遍历结束返回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

两者对比可归纳如下：

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「删除排序链表中的重复元素」是链表基础题中的高频面试题，其价值在于训练三个能力：

1. 利用有序性简化问题——重复元素必相邻，无需额外容器；
2. 指针跳接删除节点——curr.next = curr.next.next，删除后原地不动的细节处理；
3. 边界意识——空链表、单节点链表、连续多个重复节点等场景的正确处理。

建议读者结合仓库中的 链表基础教程、链表类实现 以及 链表基础题目分类列表 中列出的反转链表、移除链表元素等题目进行系统练习，将本题的指针操作内化为链表类题目的通用基本功。

• 教程
• 文档
• 知识库