備忘録 LeetCode-82. Remove Duplicates from Sorted List II

 ## はじめに
この記事はアルゴリズム振り返り用メモ，
言語化練習用に作成した記事です．
### URL
[Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/submissions/ )
## 対象者
とくになし
## code
``` main.cpp
/**
 * 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) {
        //ダミーの値を作る
        ListNode* ptr = new ListNode(-1,head);
        
        //重なっている値をピックアップする
        ListNode* copy = head;
        vector<int> vec;
        while(copy != nullptr && copy->next != nullptr){
            if(copy->val == copy->next->val)vec.push_back(copy->val);
            copy = copy->next;
        }
        //重複している値を削除
        std::sort(vec.begin(), vec.end());
        vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
        
        //重なっている値をnextから飛ばす
        copy = ptr;
        while(copy != nullptr && copy->next != nullptr){
            //更新判定flag
            bool flag = false;
            //ピックアップした値と比べる
            for(const auto& a:vec){
                if(a == copy->next->val){
                    //一致した場合
                    //次のnodeを次の次のnodeに上書きする
                    copy->next = copy->next->next;
                    //次のnodeが変わったのでflagをtrueにしてcopyを更新しないようにする
                    flag = true;
                    break;
                }
            }
            //更新
            if(!flag)copy = copy->next;
        }
        // ダミー以外を返す
        return ptr->next;
    }
};
```
## 結果
Runtime: 25 ms, faster than 6.12% of C++ online submissions for Remove Duplicates from Sorted List II.
Memory Usage: 11.4 MB, less than 12.50% of C++ online submissions for Remove Duplicates from Sorted List II.
## 詳細
![LeetCode-82. Remove Duplicates from Sorted List II.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2736795/8b7f2b71-5149-2e8f-fde7-e2e0c6388de3.png)
#### 処理手順
一番上が引数で渡される値
1.渡される値の前にダミーの値を付ける
2.重なっている値をピックアップする
3.重なっている値をnextから飛ばす
4.ダミー以外の値を返す
#### 1.渡される値の前にダミーの値を付ける
``` main.cpp
        ListNode* ptr = new ListNode(-1,head);
```
#### 2.重なっている値をピックアップする
``` main.cpp
        ListNode* copy = head;
        vector<int> vec;
        while(copy != nullptr && copy->next != nullptr){
            if(copy->val == copy->next->val)vec.push_back(copy->val);
            copy = copy->next;
        }
        //重複した値を削除
        std::sort(vec.begin(), vec.end());
        vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
```

#### 3.重なっている値をnextから飛ばす
``` main.cpp
        copy = ptr;
        while(copy != nullptr && copy->next != nullptr){
            //更新判定flag
            bool flag = false;
            //ピックアップした値と比べる
            for(const auto& a:vec){
                if(a == copy->next->val){
                    //一致した場合
                    //次のnodeを次の次のnodeに上書きする
                    copy->next = copy->next->next;
                    //次のnodeが変わったのでflagをtrueにしてcopyを更新しないようにする
                    flag = true;
                    break;
                }
            }
            //更新
            if(!flag)copy = copy->next;
        }
```

#### 4.ダミー以外の値を返す
``` main.cpp
        return ptr->next;
```
## 参照
[動画](https://youtu.be/Y2gxc-p-KsI)
## おわりに
今回は約10分程度で解けたのでこの調子で頑張りたい