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

Reverse Words In A String Problem

LeetCode 151. Given an input string s, reverse the order...

Compare Version Numbers Problem

LeetCode 165. Given two version numbers,version1 and version2, compare them....

Valid Palindrome Problem

LeetCode 125. A phrase is a palindrome if, after converting...

Remove Duplicates from Sorted List II Problem

LeetCode 82. Given the head of a sorted linked list,...

Remove Duplicates from Sorted Array II Problem

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

Partition List Problem

LeetCode 86. Given the head of a linked list and...