/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {//排序的链表
public:
ListNode* deleteDuplication(ListNode* head) {//new 返回节点的地址,dummy指向虚拟节点
auto dummy = new ListNode(-1);dummy->next=head;
//生成虚拟头节点,头节点可能会被删除.dummy指向首节点
auto p=dummy;//指针赋值,p从虚拟头节点往后遍历,头节点可能会被删除
while(p->next){//p是最后一个节点结束
auto q=p->next;
while(q->next&&q->val==q->next->val)q=q->next;//q走到最后的相同节点
if(p->next==q)p=q;//q部分没有相同节点,p移到q的位置1-2-3
else p->next=q->next;//将重复的部分删除,p指向,q的next
//p做为开头把整个链表都看过了
}
return dummy->next;//头节点有可能被删除,从虚拟头节点的下一个节点为头节点
}
};