给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。
示例1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例2:
输入: 1->1->1->2->3
输出: 2->3
//
// Created by tannzh on 2020/8/19.
//
/*
* 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。
示例1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例2:
输入: 1->1->1->2->3
输出: 2->3
*/
#include <iostream>
//Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr) return head;
ListNode preHead(0);
preHead.next = head;
ListNode *pre = &preHead;
bool isDuplicate = false;
ListNode *p = head;
while (p->next)
if (p->val == p->next->val) {
ListNode *next = p->next->next;
delete p->next;
p->next = next;
isDuplicate = true;
} else if (isDuplicate) {
ListNode *next = p->next;
delete p;
p = next;
pre->next = p;
isDuplicate = false;
} else {
pre = p;
p = p->next;
}
if (isDuplicate) {
ListNode *next = p->next;
delete p;
pre->next = next;
}
return preHead.next;
}
};
ListNode *create_linkedlist(std::initializer_list<int> lst)
{
auto iter = lst.begin();
ListNode *head = lst.size() ? new ListNode(*iter ) : nullptr;
for (ListNode *cur=head; iter != lst.end(); cur=cur->next)
cur->next = new ListNode(*iter );
return head;
}
int main(int argc, char **argv)
{
Solution s;
ListNode *head = s.deleteDuplicates(create_linkedlist({1,1,2,2,3,4}));
for (ListNode *cur=head; cur; cur=cur->next)
std::cout << cur->val << "->";
std::cout << "\b\b " << std::endl;
return 0;
}
这道题没有太多可说的，属于基本题的扩展。
可以先参考前面的 [12. Remove Duplicates from Sorted List](../12. Remove Duplicates from Sorted List).而这道题多出的一点把戏在于，要把重复的数据删的干干净净。我的策略很简单，将重复的数据做一个标记，`isDuplicate`, 然后再删掉重复元素的基础上，最后给剩下那个光棍补上一刀。虽然有点啰嗦，但是效率还过得去。
,
