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

はじめに

この記事はアルゴリズム振り返り用メモ，
言語化練習用に作成した記事です．

URL

Remove Duplicates from Sorted List II

対象者

とくになし

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.

詳細

処理手順

一番上が引数で渡される値
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;

参照

動画

おわりに

今回は約10分程度で解けたのでこの調子で頑張りたい