82. Remove Duplicates from Sorted List II
已经是线性复杂度了，不知道为什么还是%16，可能和运行有关吧。评论里很多方法其实跑了不止一趟的，下面介绍只跑一趟的方法。思路就是：指针right向前移动，每移动一次都和left指针对比，看两个值是否一样，如果一样，则计数加一，表示存在一个重复；如果两个值不一样，将left移动到right一样的位置，舍弃掉之前[left, right)（包括left，不包括right）范围内的重复元素，然后用指针p将符合条件的结点串起来。
/**
* 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;
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *left = head, *p = dummy, *right = head;
int cnt = 0;
while (right->next) {
right = right->next;
if (left->val != right->val) {
if (cnt == 0)
p = left;
else {
p->next = right;
cnt = 0;
}
left = right;
} else cnt++;
}
if (cnt) p->next = NULL;
return dummy->next;;
}
};
