删除排序链表中的重复元素
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个已排序的链表的头节点 head。
删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。
示例 1
示例 2
模拟答题者思考
1. 暴力：遍历链表把值放进新链表或数组，遇到与上一值相同就跳过——正确，但要额外 O(n) 节点或数组，也没利用「已排序、重复值相邻」。
2. 有序性：相同值必然连成一段。对当前保留节点 curr，只要 curr.next 与 curr 同值，就说明下一个是多余副本，应摘掉。
3. 摘掉方式：不移动 curr，令 curr.next = curr.next.next，可能连续多个相同值，用内层 while curr.next and curr.val == curr.next.val 一直跳。
4. 当 curr.next 为空或值不同，说明 curr 这一段去重完成，curr = curr.next 处理下一段。
5. 与 #82 对比：本题是「每个值保留一份」；#82 是「凡重复过的值整段删除」。本题通常不需要 dummy，因为从不删掉「当前唯一的一份」。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
curr | ListNode* | 定义：结果链表中「已确认保留」的最后一个节点，初始为 head（空链表则直接返回）维护： head..curr 上每个值至多出现一次，且与 curr.next 之后的未处理段相连更新：若后继与 curr.val 相同则只改 curr.next 跳过重复节点；否则 curr = curr.next 前进 |
落码步骤
1. 若 head 为空，直接返回
2. curr = head，当 curr 非空时循环
3. 当 curr.next 存在且 curr.val == curr.next.val：curr.next = curr.next.next（可连续执行，去掉所有同值后继）
4. 否则 curr = curr.next
5. 返回 head
代码实现
# 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: Optional[ListNode]) -> Optional[ListNode]:
curr = head
while curr:
while curr.next and curr.val == curr.next.val:
curr.next = curr.next.next # 跳过与 curr 同值的后继
curr = curr.next
return headclass Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* curr = head;
while (curr) {
while (curr->next && curr->val == curr->next->val)
curr->next = curr->next->next; // 跳过与 curr 同值的后继
curr = curr->next;
}
return head;
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
每删一个重复就 curr = curr.next：会漏掉连续三个及以上同值（如 [1,1,1]），应在同值时只改 next、不前进 curr。
误用 #82 的「整段删除」或 dummy + prev：本题保留每个值的第一个出现，单指针改 next 即可。
空链表未处理：while curr 自然不执行，直接返回 head == nullptr，勿对空指针访问 curr.next。
必测边界 Case
head = [] → []
head = [1,2,3] → [1,2,3]（内层 while 不触发，curr 一路前进）
head = [1,1,1,2] → [1,2]（内层 while 需执行两次摘掉多余 1）
head = [1] → [1]