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

ソート済みの連結リスト（リンクリスト）が与えられたとき、各要素が1回だけ出現するように、すべての重複を取り除くことを考えます。

たとえば、入力が [1,1,2,3,3,3,4,5,5] の場合、出力は [1,2,3,4,5] となります。リストがすでにソートされているため、同じ値を持つノードは必ず隣接しており、隣接するノード同士を比較するだけで重複を検出できるのがポイントです。

アルゴリズムの流れ

この問題は、ダミーノードを使ったシンプルな走査で解決できます。手順は以下の通りです。

• 値が -inf（INT_MIN）の新しいノード「dummy」を作成します
• dummy の next を head（元のリストの先頭）に設定します
• curr = dummy として初期化します
• curr が NULL でない限り、以下を繰り返します
  • next = curr の次のノードとします
  • next が NULL でなく、かつ next の値が curr の値と等しい間、next を次々と進めます
  • curr の next を next に接続し直します（重複ノードをスキップ）
  • curr = next として処理を進めます
• 最後に dummy の 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(INT_MIN);
        dummy->next = head;
        ListNode * curr = dummy;
        while(curr){
            ListNode * next = curr->next;
            while(next && next->val==curr->val)
                next = next->next;
            curr->next = next;
            curr=next;
        }
        return dummy->next;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,1,2,3,3,3,4,5,5};
    ListNode *head = make_list(v);
    print_list(ob.deleteDuplicates(head));
}

入力

{1,1,2,3,3,3,4,5,5}

出力

[1, 2, 3, 4, 5]

計算量について

このアルゴリズムは、リスト内の各ノードを一度だけ訪問するため、時間計算量は O(n) です。また、ダミーノード1つ分の追加メモリしか使用しないため、空間計算量は O(1) となり、非常に効率的な解法といえます。