[recommend for beginners]C++ implementation with detailed explaination


  • 5

    At the first glance, we can use the similar code of the simpler problem : which only delete the duplicate ones, So if we want to delete all the duplicate ones including the copy. We can use the dummy node and the pre pointer to jump over all the duplicate nodes.
    The Trap is that you may ignore that when we meet the no-duplicate numbers, we should do different op based the previous states. Just like state-machine.
    At last but not least important, we should delete the duplicate number occurs at the end .

    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if(!head)   return NULL;
            ListNode* dummy=new ListNode(INT_MAX);
            dummy->next=head;
            ListNode* pre=dummy, *cur=head, *next=head->next;
            bool flag=false;
            while(next){
                if(next->val==cur->val){
                    flag=true;
                    next=next->next;
                }
                else{
                    if(flag) {
                        pre->next=next;
                        cur=next;
                        next=next->next;
                    }
                    else{
                        pre=pre->next;
                        cur=cur->next;
                        next=next->next;
                    }
                    flag=false;
                }
            }
            //the corner cases : if the duplicate number locates at the end 
            if(flag) pre->next=next;
            return dummy->next;
        }
    };

  • 2
    L

    My solution has same idea, but use (pre->next == cur) as the flag.

    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if(!head) return head;
            ListNode dummy(0);
            dummy.next = head;
            ListNode *pre = &dummy;
            ListNode *cur = head;
    
            while(cur && cur->next){
                while(cur->next && cur->val == cur->next->val) cur = cur->next;
                if(pre->next == cur){
                    pre->next = cur;
                    pre = cur;
                    cur = cur->next;
                } else {
                    cur = cur->next;
                    pre->next = cur;
                }
            }
    
            return dummy.next;
        }
    };

Log in to reply
 

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