C++ Easy understand, 8ms.


  • 0
    B

    The way to solve this question is straight forward, that is : if p != p->next != p->next->next, ok, now we find one UNIQUE number:p->next.

    If we want to do like this, we must ensure p is right(case:1-1-1-2-3, p=2 is right). We need an extra bool element isDuplicated to help us. so what we want is if p != p->next != p->next->next && isDuplicated == false

    now the solution is stated as follows:

    1.make p as the unique element so far, q goes fast to check every element.

    2.if p != p->next != p->next->next && isDuplicated == false, OK good, we find an unique element, so p->next = q, keep going

    3.else, some situations may occurs:

    1> q == q->next, set isDuplicated=true,(case:1,2,3,3,4, where p = 2, q = 3)

    2> q != q->next && isDuplicated, q->next meet a new one, (case: 1,2,3,3,4,5, where p = 2, q = 3)but we don't know whether it's not duplicated, so we just unset isDuplicated=false, showing that a new one comes

    3> q != q->next && !isDuplicated, good, a unique element comes.

    class Solution {
    public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head)   return head;
        if(head && !head->next) return head;
        ListNode* fakeHead = new ListNode(-1);
        fakeHead->next = head;
        ListNode* p = fakeHead;
        ListNode* q = p->next;
        bool isDuplicated = false;
        while(q->next) {
            if(p->val != q->next->val && q->val != q->next->val && !isDuplicated) {
                p->next = q;
                p = p->next;
            }
            else {
                if(q->val == q->next->val) {
                    isDuplicated = true;
                }
                else {
                    if(isDuplicated) {
                        isDuplicated = false;
                    }
                    else {
                        p->next = q;
                        p = p->next;
                    }
                }
            }
            q = q->next;
        }
        if(isDuplicated) {
            p->next = NULL;
        }
        else {
            p->next = q;
        }
        return fakeHead->next;
        
    }
    

    };


  • 0

    Thanks for your sharing.And in your codes,at the bottom,"if(isDuplicated){p->next=NULL;}else{p->next=q;}",i think you can delete "else{p->next=q;}",because if isDuplicated==false,p->next is already equal to q .(Sorry for my poor English.)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.