Is this the best C++ solution?


  • 27
    T
    class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            ListNode **runner = &head;
            
            if(!head || !head->next)return head;
            
            while(*runner)
            {
                if((*runner)->next && (*runner)->next->val == (*runner)->val)
                {
                    ListNode *temp = *runner;
                    while(temp && (*runner)->val == temp->val)
                        temp = temp->next;
                    
                    *runner = temp;
                }
                else
                    runner = &((*runner)->next);
            }
            
            return head;
        }
    };

  • 1
    J

    To answer your question, I really think that this is the best C++ solution for this problem: no dummy heads, and double pointer makes this solution just perfect, I would say. Great!


  • 0
    L

    a novel insight into the problem. But actually the if is the key to the solution. if a duplicate is detected,firstly move to the next different number, and link it to its prefix.


  • 17
    L

    If using a fake head, like this. The idea is the same, if a duplicate is detected,firstly move to the next different number, and link it to its prefix.

    class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            ListNode fakeHead(0);
            fakeHead.next = head;
            ListNode* pre = &fakeHead;
            ListNode* p = pre->next;
            while (p ) {
                ListNode* pn = p->next;
                
                if (pn && p->val == pn->val) {
                    // move pn to next different value
                    while (pn && p->val == pn->val) {
                        pn = pn->next;
                    }
                    
                    p = pn;
                    pre->next = p;
                }
                else {
                    pre = p;
                    p = p->next;
                }
            }
            return fakeHead.next;
        }
    };

  • 4
    C

    Shouldn't we free the deleted node ? Your code is beautiful anyway!


  • 0
    H

    Actually a beautiful solution . get it!


  • 1
    A

    Clever code.Mybe this is better.
    ListNode *temp = *runner;
    int data = temp->val;
    while(temp && data == temp->val)
    {
    ListNode * p = temp;
    free(p);
    temp = temp->next;
    }


  • 0
    H

    in C ?

    struct ListNode* deleteDuplicates(struct ListNode* head) {
        struct ListNode** pNode = &head;
        if (!head || !head->next) return head;
    
        while (*pNode) {
            if ((*pNode)->next && (*pNode)->val==(*pNode)->next->val) {
                struct ListNode* node = *pNode;
                int val = node->val;
                while (node && node->val==val) {
                    struct ListNode* tmp = node;
                    node = node->next;
                    free(tmp);
                }
                *pNode = node;
            } else {
                pNode = &((*pNode)->next);
            }
        }
        return head;
    }

  • 1
    P

    It can be simplified!

    ListNode* deleteDuplicates(ListNode* head) {
        ListNode **runner = &head;
        while (*runner) {
            if ((*runner)->next && (*runner)->next->val == (*runner)->val) {
                while ((*runner)->next && (*runner)->next->val == (*runner)->val)
                    (*runner)->next = (*runner)->next->next;
                (*runner) = (*runner)->next;
            } else 
                runner = &((*runner)->next);
        }
        return head;
    }

  • 4
    Y

    Some people does't like dummy node.
    Personally I like it because it could improve readability.
    Here is my sample code with dummy node using the same methodology.

    ListNode* deleteDuplicates(ListNode* head) {
            if(!head || !head->next) return head;
            ListNode dummy(head->val+1),*pre(&dummy),*cur(head);
            dummy.next = head;
            while(cur){
                if(cur->next && cur->val == cur->next->val){
                    int cur_val = cur->val;
                    while(cur && cur->val == cur_val) cur = cur->next;
                    pre->next = cur;
                } else {
                    pre = cur;
                    cur = cur->next;
                }
            }
            return dummy.next;
        }

  • 0
    S

    This line confuses me:

    runner = &((*runner)->next);

    So you advance runner by taking the address of the next node? Wouldn't that be a ListNode*?


  • 0
    S

    I think my code is clear.

    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr)
            return nullptr;
        ListNode **p1 = &head;
        ListNode **p2 = &head;
        while(*p2 != nullptr)
        {
            if((*p2)->val != (*p1)->val)
            {
                if((*p1)->next != *p2)
                    *p1 = *p2;
                else
                    p1 = p2;
            }
            p2 = &(*p2)->next;
        }
        if((*p1)->next != *p2)
            *p1 = *p2;
        return head;
    }

  • -1
    L

    what about mine:

    bool isPowerOfFour(int num)
    {
    	int mask = 0x55555555;  // if you do 4^0 + 4^1 + 4^2 + 4^3 +..... in calc.exe in hex form
    							// you will find this magical principle.
    							// every time when add, the result is in form like "010101010101"
    							// So, 0x55555555 can be the mask to see 
    							// whether the num is partly matching power of 4
    	if (num == 0)           // Special case.
    		return false;
    	if (num & (num - 1))    // Every num which is power of 4 just has one 1bit in its binary form
    		return false;       // num & (num - 1) can judge if it is only one 1bit in its Binary
    	if (num & (~mask))      // nums which can fit "only one 1 bit in its Binary" and "the 1 Bit
    		return false;       // is at correct position" are the power of 4.
    	else
    		return true;
    }

  • 0
    D

    Same as yours Imaging!!! isn't it? But mine is more readable.
    https://leetcode.com/discuss/109725/simple-solution-because-failed-interview-using-likely-methon


  • 1
    W

    I got one question. I got 8ms running time when I ran @tommy1122337 's solution. However, I got 12ms by simply replacing the code
    if((*runner)->next && (*runner)->next->val == (*runner)->val)
    by
    if((*runner)->next && (*runner)->val == (*runner)->next->val).

    Can anyone tell me why this happen? Thanks.


  • 0

    @wen_chieh Sometimes the underlying optimiser works better in certain circumstances even space or line feed can have an influence at times. Hope someone can provide more details on this, funny question indeed.


  • 0
    R

    @tommy1122337 and everyone,

    I am just wondering, is it the use of ListNode **runner (double pointer) nesscarry?
    can i simply use single pointer?


  • 0
    Q

    use one double pointer, no temp pointer, though the triple while loop looks weird

    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            ListNode **p = &head;
            while(*p) {
                while( (*p) && (*p)->next && (*p)->val == (*p)->next->val) {
                    int val = (*p)->val;
                    while((*p) && (*p)->val == val) {
                        (*p) = (*p)->next;
                    }
                }
                if(*p) {  //if (*p) could be null, must be careful.
                    p = &((*p)->next);
                }
            }
            return head;
        }
    };

  • 2
    D

    I find use:

    ListNode *temp = (*runner)->next->next;
    

    instead of your:

    ListNode *temp = *runner;
    

    will save much time.
    finally,thanks for your sharing ~


  • 0
    L

    A readable, correct one maybe best, if you free the memory.
    Do not forget what are we pursuit of originally.


Log in to reply
 

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