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

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

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

推荐阅读:
5 Beginner’s Tips to Building a WordPress Blog  8 Best Affiliate Marketing Plugins For Your Blog  How Many Squares/Rectangles Does a Rubik Cube Have?  Find the 10001st Prime Number  The Difference Between Sum of Squares and Square of the Sum  Number of Steps to Reduce a Number in Binary Representation to O  Recursive Depth First Search Algorithm to Compute the Diameter o  Find the largest palindrome From the product of two 3-digit numb  What is the largest prime factor of the number 600851475143 ?  Can we Construct K Palindrome Strings? 
评论列表
添加评论