题目的主要信息：

• 在一个非降序的链表中，存在重复的结点，删除该链表中重复的结点，重复的结点不保留
• 进阶要求：时间复杂度：$O(n)O(n)$，空间复杂度：$O(n)O(n)$

方法一：哈希表

具体做法：

可以遍历一次链表用哈希表记录每个结点值出现的次数，然后在链表前加一个结点值为0的表头（返回的时候，直接返回res->next，加表头是为了防止删除时全部结点删完了）。再次遍历该链表，对于每个结点值检查哈希表中的计数，只留下计数为1的，其他情况都删除。

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead == NULL) //空链表
            return NULL;
        unordered_map<int, int> mp;
        ListNode* cur = pHead;
        while(cur != NULL){ //遍历链表统计每个结点值出现的次数
            mp[cur->val]++;
            cur = cur->next;
        }
        ListNode* res = new ListNode(0);
        res->next = pHead; //在链表前加一个表头
        cur = res;
        while(cur->next != NULL){ //再次遍历链表
            if(mp[cur->next->val] != 1) //如果结点值计数不为1
                cur->next = cur->next->next; //删去该结点
            else
                cur = cur->next; 
        }
        return res->next; //去掉表头
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表结点数，一共两次遍历，unordered_map每次计数、每次查询都是$O(1)O(1)$
• 空间复杂度：$O(n)O(n)$，最坏情况下$nn$个结点都不相同，哈希表长度为$nn$

方法二：直接比较删除

具体做法：

其实在遍历链表的时候也可以直接删除，因为这是一个升序链表，重复的结点都连在一起。

同样给链表前加上表头，然后遍历，如果遇到了两个相邻结点相同，则新开内循环将这一段所有的相同都遍历过去，第一个相同前的结点直接连上第一个不相同值的结点。

返回时依然要去掉表头。

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead == NULL) //空链表
            return NULL;
        ListNode* res = new ListNode(0);
        res->next = pHead; //在链表前加一个表头
        ListNode* cur = res;
        while(cur->next != NULL && cur->next->next != NULL){ 
            if(cur->next->val == cur->next->next->val){ //遇到相邻两个结点值相同
                int temp = cur->next->val;
                while (cur->next != NULL && cur->next->val == temp) //将所有相同的都跳过
                    cur->next = cur->next->next;
            }
            else 
                cur = cur->next;
        }
        return res->next; //返回时去掉表头
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表结点数，只有一次遍历
• 空间复杂度：$O(1)O(1)$，只开辟了临时指针，没有额外空间