82. 删除排序链表中的重复元素 II

Problem: 82. 删除排序链表中的重复元素 II

思路

存储每个元素出现的次数，链表中只能存在只出现一次的元素。

解题方法

用map存储每个元素出现的次数，然后重新创建链表，很暴力。。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$ 遍历链表

空间复杂度:

添加空间复杂度, 示例： $O(n)$ map

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        auto cur = head;
        map<int, int> mp;
        while(cur){
            mp[cur -> val] ++;
            cur = cur -> next;
        }

        auto dummy = new ListNode(-1);
        auto now = dummy;
        for (auto [k,v]: mp){
            if (v != 1) continue;
            auto node = new ListNode(k);
            now -> next = node;
            now = node;
        }
        
        return dummy -> next;
    }
};

过于暴力
优化:因为是有序，所以相邻元素必定挨着。如果当前位置a的下一个元素b与下一个元素c相等，那么当前位置的next指针应该指向c，重复此操作直到没有一样的元素。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;

        auto dummy = new ListNode();
        dummy -> next = head;
        auto cur = dummy;
        while(cur->next && cur->next->next){
            if (cur->next->val == cur->next->next->val){
                int x = cur->next->val;
                while(cur -> next  && cur -> next -> val == x){
                    cur -> next = cur -> next -> next;
                }
            }
            else{
                cur = cur -> next;
            }
        }
        return dummy->next;
    }
};