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)
        ListNode dummy(0); = head;
        for (auto p = head, q = &dummy; p; p = p->next)
            if (count[p->val] > 1) {
                q->next = p->next;
            else {
                q = p;

Log in to reply

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