# 82. Remove Duplicates from Sorted List II

## 1.問題

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNcivxVEXEeloBWtcTW%2F-LNcrzpIJl00aR2-N3vh%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-30%20%E4%B8%8B%E5%8D%881.07.18.png?alt=media\&token=bc5cc72d-bb80-49ac-8e85-db5270aa1735)

## 2.想法&#x20;

* 提問:
* function header, parameter
* test input
* 說明想法&#x20;
  * **用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;
    }
};
```
