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

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

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

推荐阅读：
Blogger Skills: LinkedIn and Microsoft’s Digital Skill Programs 　 5 Tips for Creating a Content Strategy for Your eCommerce Websit　 5 Tips You Can Use to Launch a Successful Property Management Bl　 Blogging and Gaming Finally Recognized as Professions　 5 Ways to Increase Blogging Productivity　 4 Ways to Build an Audience for Your New Blog　 3 Times Social Media and Cancel Culture Helped in Snuffing Out R　 How to Track Your Time as a Freelance Blogger　 US Government on Ban TikTok: Should you worry about your blog?　 Blogging Mistakes Most Beginner Bloggers Make　
评论列表
添加评论