C++でソート済み連結リストIIから重複要素を削除する方法

ソート済みの連結リストが与えられたとき、2回以上出現した要素をすべて取り除き、1度だけ現れる要素（ユニークな要素）だけを残すことを考えます。

例えば、リストが [1,1,1,2,2,3,5,6,6,7,8] の場合、出力は [3,5,7,8] となります。これは、1・2・6 がそれぞれ複数回出現している一方で、3・5・7・8 は1度しか現れていないためです。

アルゴリズムの手順

この問題は、ダミーノード（番兵ノード）を活用することで効率的に解くことができます。手順は以下の通りです。

• 値 -1 を持つダミーノードを作成し、prev := NULL、dummyPtr := dummy と初期化します。
• head が NULL でない限り、以下を繰り返します。
  • 次ノードが存在しない、または現在の値と次ノードの値が異なる場合（ユニークな要素の場合）：
    • dummyPtr->next に head を接続します。
    • temp に head->next を保存し、head->next を NULL にして切り離します。
    • head := temp として処理を進め、dummyPtr を1つ進めます。
  • 重複が見つかった場合：
    • prev := head、head := head->next とします。
    • head が NULL でなく、かつ head の値が prev の値と等しい間、両方のポインタを進め続け、重複ブロック全体をスキップします。
• 最後に、ダミーノードの next を結果として返します。

C++での実装例

以下のコードを実行すると、実際の動作をより深く理解できます。

#include <bits/stdc++.h>
using namespace std;
class ListNode{
    public:
        int val;
        ListNode *next;
        ListNode(int data){
            val = data;
            next = NULL;
        }
    };
    ListNode *make_list(vector<int> v){
        ListNode *head = new ListNode(v[0]);
        for(int i = 1; i<v.size(); i++){
            ListNode *ptr = head;
            while(ptr->next != NULL){
                ptr = ptr->next;
            }
            ptr->next = new ListNode(v[i]);
        }
        return head;
    }
    void print_list(ListNode *head){
        ListNode *ptr = head;
        cout << "[";
        while(ptr){
        cout << ptr->val << ", ";
        ptr = ptr->next;
    }
    cout << "]" << endl;
}
class Solution {
    public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        ListNode* prev = NULL;
        ListNode* dummyPtr = dummy;
        ListNode* nextNode;
        while(head){
            if(!head->next || head->val != head->next->val){
                dummyPtr->next = head;
                ListNode* temp = head->next;
                head->next = NULL;
                head = temp;
                dummyPtr = dummyPtr->next;
            } else {
                prev = head;
                head = head->next;
                while(head && head->val == prev->val){
                    prev = head;
                    head = head->next;
                }
            }
        }
    return dummy->next;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,1,1,2,2,3,5,6,6,7,8};
    ListNode *head = make_list(v);
    print_list(ob.deleteDuplicates(head));
}

入力

[1,1,1,2,2,3,5,6,6,7,8]

出力

[3, 5, 7, 8]

このアルゴリズムの計算量は、リストを一度走査するだけでよいため O(n) となり、追加の領域もポインタ数個分のみで済むため、非常に効率的な手法といえます。