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

记住，是删除结点，所以至少需要三个指针，p、cur、q。可以设置一个yummyhead结点来保证循环的一致性，在循环的过程中，可以保证p结点和cur结点永远不相同，只比较cur和q即可。当cur和q相等时，用一个循环寻找第一个和cur不相等的q结点，让p结点指向q结点即可，这样就删除中间重复的cur结点，接下来如果q还存在，则指针后移。

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        // 不要浪费时间了 求你了
        // 删除重复元素
        // 一遍扫描，记录第一次出现的元素，如果下一次元素不同，则更新，如果相同，则删除，所以同时要记录第一次出现元素之前的结点
        if (!head || !head->next) {
            return head;
        }

        // 后插法要更简单一些
        ListNode *yummyhead = new ListNode(-1);
        yummyhead->next = head;  // 给链表加上伪头结点
        ListNode *p = yummyhead;
        ListNode *cur = head, *q = head->next;
        yummyhead->next = head;
        while (q) {
            if (cur->val != q->val) {
                // 至少比较三个才能知道值是否是唯一出现的，可以保证p和cur一定不相等
                // 相等，后移即可
                p = cur;
                cur = q;
                q = q->next;    
            }
            else {
                // 相等，就往后找直到找到第一个不相等的元素为止
                while (q && cur->val == q->val) {
                    q = q->next;
                }
                // 现在q和cur不相等
                // 需要后移指针,将中间的结点都删除
                // 判断到底是空退出的还是找到了第一个不相等的元素

                p->next = q;
                if (q) {
                    cur = q;
                    q = q->next;
                }

            }
            // 可以保证p结点和cur结点不相等

        }
        // 本来就不需要加入，你这把新建一个链表和删除链表中的值搞混了
        return yummyhead->next;
    }

    ListNode *create(vector<int> vec) {
        ListNode* yummyhead = new ListNode(-1);
        ListNode* cur = yummyhead;
        for (int val : vec) {
            cur->next = new ListNode(val);
            cur = cur->next;
        }
        return yummyhead->next;
    }
};