题解 | #删除有序链表中重复的元素-II#

NC24 删除有序链表中重复的元素-II

题意分析：

给一个有序的链表，删除其中出现的重复元素

示例：链表1→2→3→3→4→4→5, 删除重复元素后，变为1→2→5。
解释：在原有链表中，3和4出现了多次，因此把所有的3,4都删除，最后返回了1→2→5。

题解一（遍历）：

在NC25中，我们删除了重复的元素，并且保留了一个，在这一题中，我们需要将所有出现的重复元素删除，我们可以在NC25上更进一步，在最后把重复元素删掉之后，再删掉保留的重复元素。
图片说明

在中间一幅图删掉1后，变成第三张图。这是我们发现指针flag与p不相同且值不同，这时就要删除掉flag指向的元素。但flag是链表头元素，删掉就没法访问链表了。

这里我们设置一个伪链表头，指针dummy，指向head。

图片说明

按照之前删除重复元素删除flag指向的元素。

我们初始化四个个指针：指针dummy指向head，用作伪头，最后用于返回结果。指针q指向flag前一个元素。指针flag指向重复的元素，指针p用于遍历链表。整体步骤如下：

删除重复元素（NC25）
删除保留的重复过的元素，我们使用一个bool变量t表示flag指针值是否被重复过了。为真，删除指针flag，为假则pass。

代码实现如下：

ListNode* deleteDuplicates(ListNode* head) {
        ListNode *flag = head;
        ListNode *p = head;
        ListNode *dummy = new ListNode(INT_MIN);
        dummy->next = head;
       ListNode *q = dummy;
        bool t = false;
        while(p){
            if(flag==p){
                p = p->next;
            }
            else if(flag!=p&&flag->val!=p->val&&!t){
                q = flag;
                flag = p;
            }
            else if(flag!=p&&flag->val!=p->val&&t){
                q->next = flag->next;
                free(flag);
                flag = q->next;
                t = false;
            }
            else if(flag!=p&&flag->val==p->val){
                t = true;
                flag->next = p->next;
                free(p);
                p = flag->next;
            }
        }
        if(t){
                 q->next = flag->next;
                free(flag);
                flag = q->next; 
        }
        return dummy->next;
    }

时间复杂度： $O(n)$ 。我们只遍历了一遍链表

空间复杂度： $O(1)$ 。我们额外申请了4个指针。常量空间。

题解二（使用set）

我们先遍历一遍链表，找出重复过的元素，存入到set中，之后再遍历一遍链表，如果该元素出现在set中，我们就不保留该结点，如果没有，我们就保留。

ListNode* deleteDuplicates(ListNode* head) {
        // write code here
         ListNode* dummy = new ListNode(-100);
        dummy->next = head;
        ListNode* p = dummy,*q=head;
        set<int>v;
        while(p&&q){
            if(p->val==q->val){
                v.insert(p->val);
                q = q->next;
            }
            else{
                p = q;
                q = q->next;
            }
        }
        p = dummy,q=head;
        while(p&&q){
            if(v.find(q->val)!=v.end()){
                p->next= q->next;
                free(q);
                q = p->next;
            }
            else{
                p = q;
                q = q->next;
            }
        }
        return dummy->next;
    }

时间复杂度 $O(nlg \ n)$ 。set的查询复杂度为 $O(lg n)$ 我们在遍历链表时候，每一次都对set发起了一次查询。所有总的时间复杂度为 $O(nlg \ n)$ 。

空间复杂度：与重复过的元素有关。