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

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

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) —

推荐阅读：
贝壳里的沙子　 过除夕的作文　 父亲，我爱你！作文450字　 我最喜欢的一本书300字　 描写龙泉洞的作文　 越长达，越明白　 打气球作文400字　 趣味第二课堂　 生命·健康·珍惜作文400字　 岳阳楼记原文及翻译　
评论列表
添加评论