An intuitive and simple solution accepted best in C, well-commented


  • 1
    //AC - 4ms;
    struct ListNode *deleteDuplicates(struct ListNode* head)
    {
        if(!head || !head->next) return head; //needless to handle;
        struct ListNode *newHead = (struct ListNode*)malloc(sizeof(struct ListNode)); //we need a head node for more convenient handling needless to consider the first node separately now ^^;
        newHead->next = head;
        struct ListNode *pre=newHead, *cur=head;
        int preVal = head->val-1; //record the previous value of the current node, the default value should affect the first node collecting - so we set it different from head->val;
        while(cur)
        {
            if(cur->val!=preVal && (!cur->next||cur->next->val!=cur->val)) //only when both the previous value and the next are not equal to the current one - by the way, the next node is null will definitely considered unequal, we can then collect it;
            {
                pre->next = cur;
                pre = pre->next;
            }
            preVal = cur->val;
            cur = cur->next;
        }
        pre->next = NULL; //terminate the list;
        return newHead->next;
    }

  • 0
    M

    My solution is the same as yours. but I am stuck in how to handle the memory deallocation.


  • 0
    This post is deleted!

  • 0

    @missshirly if you strongly think it's necessary to free the memory than, you can just store the next of the cur pointer and then update the preVal properly as follows:

    struct ListNode *deleteDuplicates(struct ListNode* head)
    {
        if(!head || !head->next) return head; //needless to handle;
        struct ListNode *newHead = (struct ListNode*)malloc(sizeof(struct ListNode)); //we need a head node for more convenient handling needless to consider the first node separately now ^^;
        newHead->next = head;
        struct ListNode *pre=newHead, *cur=head, *next;
        int preVal = head->val-1; //record the previous value of the current node, the default value should affect the first node collecting - so we set it different from head->val;
        while(cur)
        {
            next = cur->next;
            if(cur->val!=preVal && (!cur->next||cur->next->val!=cur->val)) //only when both the previous value and the next are not equal to the current one - by the way, the next node is null will definitely considered unequal, we can then collect it;
            {
                pre->next = cur;
                pre = pre->next;
                preVal = cur->val;
            }
            else
            {
                preVal = cur->val;
                free(cur);
            }
            cur = next;
        }
        pre->next = NULL; //terminate the list;
        return newHead->next;
    }
    

  • 0

    @missshirly you can just check the next answer of this question, may it be helpful!


Log in to reply
 

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