Iterative cpp solution with real O(n) time


  • 0

    Without using a hashmap, you have to walk through the linked list and check each node for whether there is another with the same value, and that requires another walk through. ie., in O(n^2) time.

    My following code uses a hashmap to store the number of each value. Then remove those with the number greater than 1.

    ListNode *deleteDuplicates(ListNode *head) {
        unordered_map<int, int> count;
    
        for (auto p = head; p; p = p->next)
            count[p->val]++;
    
        ListNode dummy(0);
        dummy.next = head;
    
        for (auto p = head, q = &dummy; p; p = p->next)
            if (count[p->val] > 1) {
                q->next = p->next;
            }
            else {
                q = p;
            }
    
        return dummy.next;
    }

Log in to reply
 

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