Straightforward O(N) Dummy Head Solution - C++


  • 0
    C

    The idea is focusing on the current node pointed by p and p's next node. If they are identical, we free the current node at p after move forward p by 1 (new p). Then we link prev_p (previous node to p) to new p. To deal with the last one duplicated node, we use variable dup to keep track of what should be deleted.

    P.S: Most solutions I see do not delete/free duplicated node. They just skip it and relink, which would be
    questioned as C++ doesn't support Garbage Collector as Java does!

    class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            
            if (!head) return NULL;
            if (!head->next) return head;
            
            ListNode *dummy = new ListNode(0);
            dummy->next = head;
            
            int dup = INT_MAX;
            
            ListNode *prev_p = dummy, *p = head;
            
            while (p)
            {
                // current p will be deleted
                if ((p->next && p->val == p->next->val) || p->val == dup)
                {
                    dup = p->val;
                    ListNode *duplicate = p;
                    prev_p->next = p->next;
                    p = p->next;
                    
                    delete duplicate;
                }
                // forward p by 1
                else {
                    
                    prev_p = prev_p->next;
                    p = p->next;
                }
            }
    
            return dummy->next;
        }
    };

  • 0
    C

    Just a small question: in C++ do you also have to delete the new created node "dummy"?


Log in to reply
 

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