83. 删除排序链表中的重复元素
题目描述
输入一个升序链表的头节点 head。链表用数组表示，例如 [1,2,3]。
对于重复出现的值，只保留一个节点，其余的删掉，使每个值恰好出现一次。
返回处理后的链表，它仍然是升序的。
示例 1
输入：head = [1,1,2] 输出：[1,2]
解释：两个 1 只留一个。
示例 2
输入：head = [1,1,2,3,3] 输出：[1,2,3]
解释：1 和 3 各去掉一个重复节点。
数据范围
- 节点数在
[0, 300]范围内。 -100 <= Node.val <= 100- 保证链表按升序排列。
解题思路
链表有序，相同的值一定挨在一起。用 cur 从头走：如果 cur.next 与 cur 值相同，就把 cur.next 跳过（cur 不动，继续比较新的 cur.next）；否则 cur 前进。每个值保留第一次出现的节点，头节点不会被删，所以不需要哑节点。
为什么正确
head 到 cur 这一段没有重复值，且 cur 是其中最大的值。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
删除后 cur 不能前进，否则连续三个相同值时会漏删一个。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur and cur.next:
if cur.next.val == cur.val:
cur.next = cur.next.next
else:
cur = cur.next
return headclass Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.next.val == cur.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* cur = head;
while (cur && cur->next) {
if (cur->next->val == cur->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.Next.Val == cur.Val {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return head
}var deleteDuplicates = function(head) {
let cur = head;
while (cur && cur.next) {
if (cur.next.val === cur.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
};function deleteDuplicates(head: ListNode | null): ListNode | null {
let cur = head;
while (cur && cur.next) {
if (cur.next.val === cur.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}