82. 删除排序链表中的重复元素 II
2021年3月25日
数据量300，数据大小[-200，200]
题意很简单，就考验你指针的使用。
两种方法
桶排序暴力法
思路很简单，加个100的偏移量，然后全都存下来，再倒着存进链表里返回即可。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
vector<int>v(201);
while(head){
v[head->val+100]++;
ListNode* tmp=head;
head=head->next;
delete(tmp);
}
for(int i=200;i>=0;i--)
if(v[i]==1){
ListNode* tmp=new ListNode(i-100,head);
head=tmp;
}
return head;
}
};
双（三）指针法
嗯，也没什么难理解的。
新建一个头指针指向head，然后从头到尾遍历。
对于[3,3,3]
我们在while里处理成[3]
再令pre->next=p(3)->next，再给它叉掉就完事了
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *pre=new ListNode(0,head);
ListNode *dump=pre;
ListNode *p=head;
while(p&&p->next){
if(p->val==p->next->val){
while(p->next&&p->val==p->next->val){
ListNode *tmp=p->next;
p->next=tmp->next;
delete(tmp);
}
pre->next=p->next;
delete(p);
}
else
pre=p;
p=pre->next;
}
head=dump->next;
delete(dump);
return head;
}
};