> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/82.-remove-duplicates-from-sorted-list-ii.md).

# 82. Remove Duplicates from Sorted List II

## 1.問題

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

![](/files/-LNcrzpIJl00aR2-N3vh)

## 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;
    }
};
```