C++でリンクリストをフラット化する方法【ソート済みリストの統合】

この問題では、right と down という2つのポインタを持つノードで構成されるリンクリストが与えられます。

• rightポインタ： メインとなるリンクリストをつなぐためのポインタです。
• downポインタ： そのノードから始まるサブリンクリストをつなぐためのポインタです。

すべてのリンクリストはそれぞれソート済みであるものとします。求められているのは、これらの複数のリンクリストを1本のリストにまとめる（フラット化する）プログラムを作成することです。そして、結果として得られるリストもソート済みの状態になっていなければなりません。

問題の例

入力：

出力：

1-> 9-> 8 -> 4 -> 6-> 7-> 2-> 3-> 5

解法アプローチ

この問題を効率的に解くための有力な手法が、リンクリスト版のマージソートを応用する方法です。各サブリストを再帰的にマージしながら統合していくことで、最終的に1本のソート済みリスト（フラット化されたリスト）を形成します。

具体的には、メインリスト（right方向）をまず末尾まで再帰的にたどり、戻りながら隣接する2つのリストを順番にマージしていきます。こうすることで、すべての要素が昇順につながった単一のリストが完成します。

アルゴリズムの手順

1. 再帰的に right 方向の次のノードへ進みます。
2. リストの末端に到達したら、そこから戻りながら現在のリストと次のリストをマージします。
3. マージ処理では down ポインタ先の値を比較し、小さい方から順につないでいきます。このとき right ポインタは NULL に設定します。
4. すべてのマージが完了すると、down ポインタだけでつながった1本のソート済みリストが得られます。

C++による実装例

以下は、上記の解法の動作を示すプログラムです。

#include <bits/stdc++.h>
using namespace std;

class Node{
    public:
    int data;
    Node *right, *down;
};
Node* head = NULL;
Node* mergeList(Node* a, Node* b){
    if (a == NULL)
        return b;
    if (b == NULL)
        return a;
    Node* result;
    if (a->data < b->data){
        result = a;
        result->down = mergeList(a->down, b);
    }
    else{
        result = b;
        result->down = mergeList(a, b->down);
    }
    result->right = NULL;
    return result;
}
Node* flattenLinkedList(Node* root){
    if (root == NULL || root->right == NULL)
        return root;
    root->right = flattenLinkedList(root->right);
    root = mergeList(root, root->right);
    return root;
}
Node* push(Node* head_ref, int data){
    Node* new_node = new Node();
    new_node->data = data;
    new_node->right = NULL;
    new_node->down = head_ref;
    head_ref = new_node;
    return head_ref;
}
int main(){
    head = push(head, 7);
    head = push(head, 1);
    head->right = push(head->right, 11);
    head->right = push(head->right, 5);
    head->right = push(head->right, 4);
    head->right->right = push(head->right->right, 12);
    head->right->right = push(head->right->right, 6);
    head->right->right->right = push(head->right->right->right, 8);
    head->right->right->right->right = push(head->right->right->right->right, 16);
    head = flattenLinkedList(head);
    cout<<"The Flattened Linked list is : \n";
    Node* temp = head;
    while (temp != NULL){
        cout<<temp->data<<" => ";
        temp = temp->down;
    }
    cout<<"NULL";
    return 0;
}

実行結果

The Flattened Linked list is :
1 => 4 => 5 => 6 => 7 => 8 => 11 => 12 => 16 => NULL

計算量について

この実装では、リストを後ろから順に1本ずつマージしていくため、全ノード数を N、サブリストの本数を M とすると、最悪の場合の時間計算量は O(N×M) となります。一方、リスト同士をマージソートのようにペアごとに統合する分割統治法を用いれば、O(N log M) まで改善できます。また、再帰呼び出しを使用しているため、サブリストの本数に比例した最大 O(M) のスタック領域が必要になる点にも注意してください。