题解 | #删除有序链表中重复的元素-II#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next) return head;
        auto dummy=new ListNode(1010);
        dummy->next=head;
        auto q=dummy, p=head;
        while(p)
        {
            if(p->next && p->val==p->next->val)
            {
                auto t=p;
                while(p && p->val==t->val) p=p->next;
                q->next=p;
            }
            else
            {
                p=p->next;
                q=q->next;
            }
        }
        return dummy->next;
    }
};

1. 由于可能需要删除头结点，因此在头部添加一个虚拟节点dummy；
2. 使用q指向需要删除的一段元素的前继；t指向删除区间的开始，用于对比是否q需要向后移动；q指向删除区间的下一元素（这里只要q不为null且与t的val相同就向后移动）
3. 令q->next=p

#### 注意

1. 要看清楚题目，是删除所有重复的元素，而不是保留重复的元素中的一个
2. 由于头结点可能会被删除，所以最后返回的是`dummy->next`而不是head