题目描述

个人感觉本题最大的难点是判断哪些元素是重复以及想到如何跨越重复元素连接到下一个非重元素处。yxc大佬的思路是加入dummy node（头结点）,从而避免边界情况（因为可能开头的元素就是重复的），本题最大的考点是双指针，这个双指针的总结如下，头指针指向当前最后一个非重复元素所在的结点pi，第二个指针指向的是下一个元素的下一个结点pj，从而通过判断pj是否为pi的next的next来判断pi和pj之间是否只有一个元素，是的话，则将pi移到pi的next，否则的话将pi的next指针指向pj，此时的做法相当于直接删除了pi和pj之间的重复元素，此处我加上delete中间元素的过程。

算法1

(双指针) $O(n)$

C++ 代码

/**
 * 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) {
        if(! head ) return head;
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        auto p = dummy;

        while(p -> next){
            auto q = p -> next;
            while(q && p -> next -> val == q -> val) q = q->next;

            if(q == p -> next -> next) p = p -> next;
            else{
                auto t1 = p -> next;
                p -> next = q;
                int v = t1 -> val;
                while(t1 && t1 -> val == v) {
                    auto t2 = t1;
                    t1 = t1 ->next;
                    delete t2;
                }
            }
        }
        return dummy -> next;
    }

};