题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。

样例

输入：1->2->3->3->4->4->5

输出：1->2->5

样例2

输入：1->1->1->2->3

输出：2->3

算法

(线性扫描)

1. 之前做的删除节点的题是有重复元素只保留１个下来，这道题的要求是一个都不保留。(有点狠兄弟)
2. 那么就要求在cur指针还没扫到重复元素区间的第一个元素的时候，就知道它们是重复元素了。
3. 那么针对于２，解决方法是新建一个指针go，go = cur->next。就像cur相当于是上帝视角，是大佬，go是小兵向前冲。一般第一步cur->next->val是一定等于go->val的，接下来是继续判断，如果有重复元素，小兵go会继续向前冲，最后碰到不同元素，跳出while循环。
4. 逻辑是这样：如果cur的后面是有一段相同元素，cur是不会涉足这段元素的，go会遍历这一段的每一个元素。最后，cur是相同元素区间的前一个节点，go是相同元素区间的后一个节点。
5. 接下来的if判断，if(cur->next->next == go)成立意味着cur和go之间没有重复元素，那么cur向前走一步。如果else成立，说明有重复元素，那么cur->next指向go，直接略过相同元素这一段，相当于删除了这一段。
6. 我的问题有２个，第１个：为什么是cur->next = go，而不是直接cur = go。
7. 第２个，dummy->next是怎么工作的，哪里改了dummy的next指向。

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        auto cur = dummy;
        while(cur->next)
        {
            auto go = cur->next;
            while(go && cur->next->val == go->val) go = go->next;
            if(cur->next->next == go) cur = cur->next;
            else cur->next = go;
        }
        return dummy->next;
    }
};