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

方法一：双指针求解

1、设置一个指针cur指向表头（为了解决表头就是重复元素的情况）；

2、若cur->next与cur->next->next是重复元素，将cur->next向后移动直到指向不等于该元素的结点。

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
  public:
    ListNode* deleteDuplicates(ListNode* head) {
        //特殊情况处理
        if (head == nullptr || head->next == nullptr)
            return head;
		//设置表头
        ListNode* res = new ListNode(0);
        res->next = head;
        ListNode* cur = res;

        while (cur->next->next && cur->next) {
            if (cur->next->val == cur->next->next->val) {
                int temp = cur->next->val;
                while (cur->next->val == temp && cur->next != nullptr)
                    cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }
        return res->next;
    }
};

方法二：哈希表求解

利用哈希表找到重复的元素，删除重复元素的结点

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
  public:
    ListNode* deleteDuplicates(ListNode* head) {
        //特殊情况处理
        if (head == nullptr || head->next == nullptr)
            return head;

        unordered_map<int, int> map;
        ListNode* cur = head;
	  	//遍历链表统计每个节点值出现的次数
        while (cur != nullptr) {
            map[cur->val]++;
            cur = cur->next;
        }
		//设置表头
        ListNode* res = new ListNode(0);
        res->next = head;
        cur = res;
		//删除重复的元素
        while (cur->next != nullptr) {
            if (map[cur->next->val] != 1) {
                cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }

        return res->next;
    }
};