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;
    }
};