82. Remove Duplicates from Sorted List II

1.問題

• 如果linked list中的元素出現超過一次, 則從list中移除

2.想法

• 提問:

• function header, parameter

• test input

• 說明想法

  • 用map記錄每個元素出現的次數, 如果超過一次則從list中移除

  • 移除node:

    • Create一個dummy node, 初始狀態下*pre指向這個node, newNode->next = head, 這樣無論是要移除哪個node等同於從list中間移除node

    • pre->next = curr->next

    • curr->next = NULL

    • pre = pre->next

• 測試計算複雜度

3.程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        map<int, int> m;
        ListNode* curr = head;
        while (curr) {
            if (m.find(curr->val) != m.end()) {
                m[curr->val]++;
            } else {
                m[curr->val] = 1;
            }
            curr= curr->next;
        }
        ListNode* tmp = new ListNode(0);
        curr = head;
        ListNode* pre = tmp;
        pre->next = curr;
        while (curr) {
            if (m[curr->val] > 1) {
                pre->next = curr->next;
                curr->next = NULL;
                curr = pre->next;
            } else {
                pre = curr;
                curr = curr->next;
            }
        }
        
        return tmp->next;
    }
};