82. 删除排序链表中的重复元素 II
题目描述
输入一个升序链表的头节点 head。链表用数组表示，例如 [1,2,3]。
如果某个值在链表里出现了不止一次，就把这个值的所有节点都删掉，一个不留。只出现一次的值保留下来。
返回删除后的链表，它仍然是升序的。
示例 1
输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]
解释：3 和 4 都重复了，全部删除，剩下 [1,2,5]。
示例 2
输入：head = [1,1,1,2,3] 输出：[2,3]
解释：1 出现三次，全部删除，剩下 [2,3]。
数据范围
- 节点数在
[0, 300]范围内。 -100 <= Node.val <= 100- 保证链表按升序排列。
解题思路
头节点也可能被删，所以在前面接一个哑节点 dummy，prev 从 dummy 开始。每轮看 cur = prev.next：如果 cur 与下一个节点值相同，说明这个值重复，把 cur 一直往后移到第一个不同的值，再让 prev.next 直接指向它，整段跳过；否则 cur 只出现一次，确认保留，prev 前进。
为什么正确
dummy 到 prev 这一段只含恰好出现一次的值，并且 prev.next 之后都是未处理的节点。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
跳过重复段后 prev 不能前进：新的 prev.next 还没检查，它自己也可能是下一段重复的开头。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
prev = dummy
while prev.next:
cur = prev.next
if cur.next and cur.next.val == cur.val:
v = cur.val
while cur and cur.val == v:
cur = cur.next
prev.next = cur
else:
prev = cur
return dummy.nextclass Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
while (prev.next != null) {
ListNode cur = prev.next;
if (cur.next != null && cur.next.val == cur.val) {
int v = cur.val;
while (cur != null && cur.val == v) {
cur = cur.next;
}
prev.next = cur;
} else {
prev = cur;
}
}
return dummy.next;
}
}class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode(0, head);
ListNode* prev = dummy;
while (prev->next) {
ListNode* cur = prev->next;
if (cur->next && cur->next->val == cur->val) {
int v = cur->val;
while (cur && cur->val == v) {
cur = cur->next;
}
prev->next = cur;
} else {
prev = cur;
}
}
return dummy->next;
}
};func deleteDuplicates(head *ListNode) *ListNode {
dummy := &ListNode{Val: 0, Next: head}
prev := dummy
for prev.Next != nil {
cur := prev.Next
if cur.Next != nil && cur.Next.Val == cur.Val {
v := cur.Val
for cur != nil && cur.Val == v {
cur = cur.Next
}
prev.Next = cur
} else {
prev = cur
}
}
return dummy.Next
}var deleteDuplicates = function(head) {
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next) {
let cur = prev.next;
if (cur.next && cur.next.val === cur.val) {
const v = cur.val;
while (cur && cur.val === v) {
cur = cur.next;
}
prev.next = cur;
} else {
prev = cur;
}
}
return dummy.next;
};function deleteDuplicates(head: ListNode | null): ListNode | null {
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next) {
let cur = prev.next;
if (cur.next && cur.next.val === cur.val) {
const v = cur.val;
while (cur && cur.val === v) {
cur = cur.next;
}
prev.next = cur;
} else {
prev = cur;
}
}
return dummy.next;
}