题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

p是我们想求的无重复链表的当前的尾节点，(p->next->next==q)表示p->next(p->next代表的点)和q两个点的的距离是一，说明中间没有重复元素，更新尾节点p=p->next;
else，表示p->next和q两个点的距离大于1，中间有重复元素，全部删除，让p->next=q;p是更新前无重复链表的尾节点，p->next=q表示删除了中间的元素，直接连到了q上。下面就要从q向后判断是否有重复了。

C++ 代码

class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        auto dummpy = new ListNode(-1);
        dummpy->next = head;
        auto p = dummpy;
        while(p->next){
            auto q = p->next;
            while(q && p->next->val == q->val) q=q->next; //如果p->next点的值和q点的值重复，q一直向后走

            //如果p->next的点和q点距离为1说明两个点的值不同,p->next这个点可以作为新的尾节点。
            //更新p=p->next, p表示无重复链表的尾节点。
            //判断两个点的距离是否为1
            if(p->next->next==q) p=p->next;
            else{//否则距离不为1，删除p->next点和q点间的所有值，即让p->next指向q。
                p->next=q;
            }
        }
        return dummpy->next;

    }
};