C++で2つのソート済み連結リストをマージする方法【サンプルコード付き】

問題の概要

ソート済みの単方向連結リストが2つ与えられます。この2つのリストを1つのソート済みリストに統合（マージ）する関数を作成してください。

List1: 10->15->17->20
List2: 5->9->13->19
Result: 5->9->10->13->15->17->19->20

アルゴリズム

基本的な考え方は、両方のリストを先頭から順に走査し、常に値の小さい方のノードを結果リストにつなげていくというものです。

1. 両方のリストを走査する
    1.1. list1->data < list2->data の場合
        1.1.1 結果リストにlist1->dataを追加し、list1のポインタを進める
    1.2. list2->data < list1->data の場合
        1.2.1 結果リストにlist2->dataを追加し、list2のポインタを進める
2. 両方のリストが尽きるまで手順を繰り返す
3. 結果のリストを返す

C++での実装例

以下は、再帰的なアプローチを用いて2つのソート済み連結リストをマージするC++プログラムの完全な例です。

#include <iostream>
#include <new>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct node {
    int data;
    struct node *next;
};
node *createList(int *arr, int n){
    node *head, *p;
    p = head = new node;
    head->data = arr[0];
    head->next = NULL;
    for (int i = 1; i < n; ++i) {
        p->next = new node;
        p = p->next;
        p->data = arr[i];
        p->next = NULL;
    }
return head;
}
void displayList(node *head){
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}
node *mergeSortedLists(node *head1, node *head2){
    node *result = NULL;
    if (head1 == NULL) {
        return head2;
    }
    if (head2 == NULL) {
        return head1;
    }
    if (head1->data < head2->data) {
        result = head1;
        result->next = mergeSortedLists(head1->next, head2);
    } else {
        result = head2;
        result->next = mergeSortedLists(head1, head2->next);
    }
    return result;
}
int main(){
    int arr1[] = {10, 15, 17, 20};
    int arr2[] = {5, 9, 13, 19};
    node *head1, *head2, *result = NULL;
    head1 = createList(arr1, SIZE(arr1));
    head2 = createList(arr2, SIZE(arr1));
    cout << "First sorted list: " << endl;
    displayList(head1);
    cout << "Second sorted list: " << endl;
    displayList(head2);
    result = mergeSortedLists(head1, head2);
    cout << "Final sorted list: " << endl;
    displayList(result);
    return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

First sorted list:
10 15 17 20
Second sorted list:
5 9 13 19
Final sorted list:
5 9 10 13 15 17 19 20

コードのポイント

この実装では、mergeSortedLists関数が再帰的に呼び出され、2つのリストの先頭ノード同士を比較しながら、値の小さい方から順に結果リストへつなげていきます。どちらか一方のリストが空になった時点で、もう一方の残りのリストがそのまま返されるため、マージ処理が完了します。

このアルゴリズムの計算量は O(n + m)（n と m はそれぞれのリストの長さ）です。新しいノードを生成せず既存のノードを再利用するため、追加のメモリ消費がほとんどない効率的な手法と言えます。