LeetCode 83. 删除排序链表中的重复元素
目录
题目描述
题意分析
给定一个升序排列的链表，删除重复出现的元素，使每个值只保留一次，返回处理后的链表。
「已排序」是本题最重要的约束信号：相同的值必然连续相邻出现，判断一个值是否重复不需要记录全局出现过什么，只需要看相邻两个节点是否相等。如果链表无序，这个前提就不成立，题目难度会完全不同。
另一个关键点是「保留一个」而不是「整组删除」——每组重复值的第一个节点留下，这意味着头节点永远安全；整组删除的版本是 82 题。边界上，空链表与单节点链表天然无重复，应原样返回。
解法：单指针跳过连续重复节点
核心思路
问题关键：链表已经升序，相同值一定连续，因此只需比较相邻节点，不需要哈希表。
用指针
cur扫描链表。若cur.val == cur.next.val，让cur.next指向下下个节点；删除后cur不动，因为新的cur.next仍可能重复。只有相邻值不同时才前进。不变量：每轮开始时，
head到cur已完成去重，cur是当前值保留下来的节点。循环结束时所有节点都被处理，因此直接返回head。本题每组保留一个，头节点不会删除，所以不需要哑节点。
解题步骤
- 令
cur = head，空链表会直接跳过循环。- 当
cur和cur.next都存在时，比较两者的值。- 值相同：执行
cur.next = cur.next.next，继续检查当前cur。- 值不同：把
cur前移一位。- 返回原头节点。以
[1,1,1,2]为例，前两个重复节点被连续跳过后，cur才会移动到2。
代码实现
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;
}
}
func deleteDuplicates(head *ListNode) *ListNode {
cur := head
for cur != nil && cur.Next != nil {
if cur.Val == cur.Next.Val {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return head
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点至多被访问一次。
- 空间复杂度：$O(1)$，原地修改指针。
关键点总结
- 利用「有序 ⇒ 重复相邻」，把全局去重变成局部比较。
- 删除重复节点后不能前进，否则会漏掉三个及以上的连续重复值。
- 本题保留每组第一个节点；若要求整组删除（82 题），头节点可能被删，需要哑节点和前驱指针。
易错点总结
- 删除后仍然前进：
[1,1,1]会残留一个重复的1。- 循环只判断
cur.next：空链表会发生空指针异常，必须先判断cur。- 返回
cur而不是head：最终只会返回尾部子链表。- 混淆 82 题：
[1,1,2]在本题应得到[1,2]，不是[2]。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 82. 删除排序链表中的重复元素 II | 中等 | 重复整组删除，哑节点加前驱指针 |
| 203. 移除链表元素 | 简单 | 按给定值删除任意匹配节点 |
| 237. 删除链表中的节点 | 中等 | 只给待删节点本身，值覆盖法删除 |
| 剑指 Offer 18. 删除链表的节点 | 简单 | 按值定位前驱后删除单个节点 |
| 面试题 02.01. 移除重复节点 | 简单 | 无序链表去重，需哈希集合记录 |
| 面试题 02.03. 删除中间节点 | 简单 | 无法访问头节点时的中间节点删除 |