My C++ code (14 ms) with detailed comments


  • 0
    D
    class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            ListNode *cur= head, *tail;
            if(head)
            {
                ListNode dummyHead(0); // use a dummy head to track real head
                tail = &dummyHead; // tail is  the last node of the new list 
            
                while(cur && cur->next) // cur= NULL only occures when the last node is a repeating node
                {// for each iteration,  it is guaranteed that cur has a  value different from its previous node (assume head also meets it)
                    if(cur->val != cur->next->val) 
                    {  // if cur also has a value different from its next node, then link it to the tail node
                        tail->next = cur;
                        tail = tail->next; // update tail
                        cur = cur->next; // move cur to its next
                    }
                    else
                    { // cur has a same value as its next, then skip all the nodes with the same value
                        while( (cur->next) && (cur->val == cur->next->val)) cur = cur->next; // cur is the last one with the same value
                        cur = cur->next; // move to its next, which has a different value from its precedence node
                    }
                }
                last->next = cur; // don't forget to link cur
                return dummyHead.next;  // return the new head
            }
            return head;
        }
    };

  • 0
    W

    you didn't free the same value node


Log in to reply
 

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