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-5Example 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) —
loading...
Last Post: How to Sort a Linked List by Converting to Array/Vector?
Next Post: Algorithm to Generate the Spiral Matrix in Clock-wise Order
