C++ with detailed explanation


  • 0
    E
    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if (!head) {
                return NULL;
            }
    // because the head node might be deleted, so use auxiliary node 
            ListNode* dummy = new ListNode(0);
            dummy->next = head;
    // start with head node
            ListNode* cur = head;
            ListNode* pre = dummy;
            while (cur) {
    // check if duplicate happens
                if (cur->next && cur->next->val == cur->val) {
    // keep the duplicate val
                   int target = cur->val;
    // every time meet the duplicate, delete it
                   while (cur && cur->val == target) {
                       pre->next = cur->next;
                       cur = cur->next;
                   }
                } else {
    // otherwise, move forward
                    pre = cur;
                    cur = cur->next;
                }
            }
    // save the return head and recycle the memory of the auxiliary node
            ListNode* ret = dummy->next;
            delete(dummy);
            return ret;        
        }
    };
    

    Time Complexity O(n)
    Space Complexity O(1) only use a auxiliary node.


  • 0
    A

    why have you added the check of pointer to be null in all test cases .. like cur&&cur->val==target and like that why its unnecessary most of the times right?


Log in to reply
 

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