Remove Duplicates from Sorted List II Problem


Description

LeetCode Problem 82.

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

1
2
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

1
2
Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if ((head == NULL) || (head->next == NULL))
            return head;
        
        ListNode* curr = head;
        map<int, int> cnt;
        while (curr != NULL) {
            if (cnt.find(curr->val) != cnt.end()) {
                cnt[curr->val] ++;
            } else {
                cnt[curr->val] = 1;
            }
            curr = curr->next;
        }

        int first_num;
        bool is_empty = true;
        for (map<int,int>::iterator mit = cnt.begin(); mit != cnt.end(); 
            mit ++) {
            if (mit->second == 1) {
                first_num = mit->first;
                is_empty = false;
                break;
            }
        }
        if (is_empty)
            return NULL;
        
        curr = head;
        ListNode* new_head;
        ListNode* prev;
        while (curr != NULL) {
            if (curr->val == first_num) {
                new_head = curr;
                break;
            }
            curr = curr->next;
        }

        prev = new_head;
        curr = new_head->next;
        while (curr != NULL) {
            if (cnt[curr->val] == 1) {
                prev->next = curr;
                prev = prev->next;
            }
            curr = curr->next;
        }
        prev->next = NULL;
        return new_head;
    }
};




Related Posts

Squares Of A Sorted Array Problem

LeetCode 977. Given an integer array nums sorted in non-decreasing...

Sort Array By Parity Problem

LeetCode 905. Given an integer array nums, move all the...

Sort Array By Parity II Problem

LeetCode 922. Given an array of integers nums, half of...

Shortest Distance To A Character Problem

LeetCode 821. Given a string s and a character c...

Reverse Only Letters Problem

LeetCode 917. Given a string s, reverse the string according...

Push Dominoes Problem

LeetCode 838. There are n dominoes in a line, and...