C++の連結リストで母音ノードを先頭へ、子音ノードを末尾へ並べ替える方法

はじめに

この記事では、連結リスト（リンクリスト）に格納された文字ノードを、母音（A・E・I・O・U）のノードは先頭側へ、子音のノードは末尾側へと並べ替える手法を解説します。ポイントは、並べ替え後も元の相対的な順序が崩れないという点です。

入力：A-M-A-Z-O-N
出力：A-A-O-M-Z-N
計算量：時間 O(N)／空間 O(1)

アルゴリズムの考え方

母音用と子音用にそれぞれダミーノード（番兵）を用意し、元のリストを先頭から順に走査します。各ノードの文字が母音であれば母音用ダミーノードの直後に、子音であれば子音用ダミーノードの直後に挿入していきます。全ノードの振り分けが完了したら、母音リストの末尾に子音リストを連結し、最後にダミーノードを取り除けば完成です。

• isVowel()：渡された文字が母音かどうかを判定する補助関数です。
• insertAfter()：指定ノードの直後に新しいノードを挿入します。
• groupByVowels()：リストを一度だけ走査し、母音ノードと子音ノードを振り分けて連結します。

リスト全体をたった一回の走査で処理できるため、時間計算量は O(N)、追加メモリもダミーノード2個分だけで済み、O(1) という非常に効率的な実装になります。

C++による実装例

#include <iostream>
using namespace std;

class Node1{
public:
    char var1;
    Node1 *next1;
    Node1(char v, Node1 *next1=NULL):var1(v), next1(next1){}
};

// 文字配列から連結リストを生成する
Node1 *make_list(char array1[], int size1){
    if(size1 == 0)
        return NULL;
    Node1 *head = new Node1('o');  // ダミーノード
    Node1 *temp = head;
    for(int i=0; i<size1; ++i){
        temp->next1 = new Node1(array1[i]);
        temp = temp->next1;
    }
    temp = head;
    head = head->next1;            // ダミーを外す
    delete temp;
    return head;
}

// リストの内容を出力する
void print_list(Node1 *head){
    while(head){
        cout<<head->var1<<"--";
        head = head->next1;
    }
    cout<<"END"<<endl;
}

// 指定ノードの直後に n を挿入する
void insertAfter(Node1** temp, Node1 *n){
    n->next1 = (*temp)->next1;
    (*temp)->next1 = n;
}

// 母音かどうかを判定する
bool isVowel(char v){
    switch(v){
        case 'A': case 'E': case 'I':
        case 'O': case 'U':
            return true;
        default:
            return false;
    }
}

// 母音ノードを先頭に、子音ノードを末尾に並べ替える
Node1 *groupByVowels(Node1 *head){
    Node1 *vowel = new Node1('L');     // 母音用ダミーノード
    Node1 *consonant = new Node1('C'); // 子音用ダミーノード
    Node1 *tv = vowel, *tc = consonant;
    for(Node1 *temp=head; temp;){
        Node1 *tt = temp->next1;      // 次ノードを退避
        if(isVowel(temp->var1)){
            insertAfter(&tv, temp);
            tv = tv->next1;
        } else {
            insertAfter(&tc, temp);
            tc = tc->next1;
        }
        temp = tt;
    }
    tv->next1 = consonant->next1;     // 母音群の末尾に子音群を連結
    Node1 *dummy = vowel;
    vowel = vowel->next1;             // ダミーを外す
    delete dummy;
    delete consonant;
    return vowel;
}

int main(){
    char array1[] = {'A','M','A','Z','O','N'};
    Node1 *head = make_list(array1, sizeof(array1)/sizeof(array1[0]));
    print_list(head);
    head = groupByVowels(head);
    print_list(head);
}

実行結果

A--M--A--Z--O--N--END
A--A--O--M--Z--N--END

まとめ

ダミーノードを使って母音グループと子音グループを同時に構築し、最後に連結するだけで、順序を保ちながら O(N) 時間・O(1) 空間での並べ替えが可能です。既存ノードのポインタを付け替えるだけで完結するため、新規ノードの確保が不要であり、メモリ効率にも優れた手法といえます。