How to Remove the Duplicates from Sorted List (Leaving Only Dist

  • 时间：2020-09-12 10:06:27
  • 分类：网络文摘
  • 阅读：131 次

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

Example 1:
Input: 1-2-3-3-4-4-5
Output: 1-2-5

Example 2:
Input: 1-1-1-2-3
Output: 2-3

Using a Hashmap to Count the Items

We can use a hashmap i.e. unordered_map in C++, to count the occurences of the items in the original linked list. This will cost O(N) time and O(N) space. However, the algorithm also applies to unsorted linked list. But it requires two passes.

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        unordered_map<int, int> count;
        ListNode* p = head;
        while (p) {            
            count[p->val] ++;
            p = p->next;
        }
        ListNode* dummy = new ListNode(-1);
        p = dummy;
        while (head) {
            if (count[head->val] == 1) {
                p->next = new ListNode(head->val);
                p = p->next;
            }
            head = head->next;
        }
        return dummy->next;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        unordered_map<int, int> count;
        ListNode* p = head;
        while (p) {            
            count[p->val] ++;
            p = p->next;
        }
        ListNode* dummy = new ListNode(-1);
        p = dummy;
        while (head) {
            if (count[head->val] == 1) {
                p->next = new ListNode(head->val);
                p = p->next;
            }
            head = head->next;
        }
        return dummy->next;
    }
};

Skipping Duplicate Items on the Fly

The fact that the linked list is sorted helps us desgin a better algorithm. We can count the occurences of the current node in the linked list. If it is more than one, then skip it, otherwise, add the current node to the previous node – which we can update iteratedly.

This approach is O(N) time and O(1) constant space requirement.

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        ListNode* prev = dummy;
        while (head) {
            int c = 0;
            ListNode *cur = head;
            while (head && head->val == cur->val) {
                c ++;
                head = head->next;
            }
            if (c == 1) {
                prev->next = cur;
                prev = cur;
            }
            cur->next = NULL;
        }        
        return dummy->next;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        ListNode* prev = dummy;
        while (head) {
            int c = 0;
            ListNode *cur = head;
            while (head && head->val == cur->val) {
                c ++;
                head = head->next;
            }
            if (c == 1) {
                prev->next = cur;
                prev = cur;
            }
            cur->next = NULL;
        }        
        return dummy->next;
    }
};

Depending on the requirements, you might want to delete the un-used nodes from the original linked list – in order to free the memory.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
鸡汤虽营养丰富，但这几种病人不要喝　 饮食健康与胃病食疗（一）：胃病患者饮食注意事项　 饮食健康与胃病食疗（二）：慢性胃炎的饮食调理　 饮食健康与胃病食疗（三）：这样饮食降低胃癌风险　 冬至时节，常吃这几种传统美食可补阳、防寒！　 只有这样吃大蒜才能杀菌防癌，以前你吃对了吗　 丝瓜营养丰富，其对人体的保健功效如此之多　 患有胃病的人常吃这些食物，可以帮助调理好胃　 山药营养丰富食疗价值高，助爱美女性吃出好身材　 糖尿病患者常有这些饮食误区，朋友们注意啦！　
评论列表
添加评论