题目描述:与83题不同的是若一个元素出现重复则将此元素全部删除,返回处理后的链表。如:
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
分析:设两个指针,第一个指向不重复的最后一个元素,第二个一边遍历链表,一边删除重复元素。虽然是两重while,但总共只遍历一遍,时间复杂度O(n),空间O(1)。
代码:
/**
* 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 head;
ListNode l(INT_MIN);
l.next = head;
ListNode *pre = &l, *cur = head;
while (cur) //遍历链表
{
bool f = false;
while ( cur -> next && cur -> val == cur -> next -> val) //从当前访问的元素找重复的长度
{
f = true;
ListNode *tmp = cur;
cur = cur -> next;
delete tmp;
}
if (f) //删除重复的最后一个元素
{
ListNode *tmp = cur;
cur = cur -> next;
delete tmp;
continue;
}
pre -> next = cur; //重新链到前段
pre = pre -> next;
cur = cur -> next;
}
pre -> next = cur;
return l.next;
}
};