82. 删除排序链表中的重复元素 II
82. 删除排序链表中的重复元素 II
难度：中等
描述：给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* res=new ListNode(0); //创建一个保存最后结果的头节点res
ListNode* r=res; //r指向res的尾节点
ListNode* cur=head; //当前节点
int length=0;
while(cur!=nullptr)
{
//当前数与下一个数若相同则继续，知道下一个数不相等位置，此时cur指向最后一个相同的数
while(cur->next!=nullptr&&cur->val==cur->next->val)
{
length++;
cur=cur->next;
}
//如果length>0说明有相同的数，此时cur指向最后一个相同的数
if(length>0)
{
cur=cur->next;
length=0;
}
//否则将当前节点加入结果节点
else{
r->next=cur;
r=cur;
cur=cur->next;
}
}
r->next=nullptr;
return res->next;
}
};
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:
ans=ListNode(0)
cur=head
length=0
r=ans
while cur:
while cur.next and cur.val==cur.next.val:
cur=cur.next
length+=1
if length>0:
cur=cur.next
length=0
else:
r.next=cur
r=cur
cur=cur.next
r.next=None
return ans.next
复杂度分析
时间复杂度：O(n)，其中n是链表的长度。
空间复杂度：O(1)
Original: https://www.cnblogs.com/fengrrr/p/16161882.html
Author: fengrrr
Title: LeetCode82. 删除排序链表中的重复元素 II
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/620702/
转载文章受原作者版权保护。转载请注明原作者出处！