Remove Duplicates from Sorted List II (C++)
1665 ワード
/**
* 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) {
if(!head) return NULL;
if(!head->next) return head;
ListNode *dh = new ListNode(0);
dh->next = head;
ListNode *pre = dh;
ListNode *last = head;
ListNode *cur = head->next;
int cn = 1;
while(cur) {
if(cur->val != last->val) {
if(cn > 1) {
while(last != cur) {
pre->next = last->next;
delete last;
last = pre->next;
}
cn = 1;
} else {
pre = last;
last = last->next;
}
} else {
cn ++;
}
cur = cur->next;
}
if(cn>1) {
while(last != cur) {
pre->next = last->next;
delete last;
last = pre->next;
}
}
cur = dh->next;
delete dh;
return cur;
}
};