C++でマルチレベル連結リストをフラット化する方法を解説

この記事では、マルチレベル連結リスト（Multilevel Linked List）をフラット化するプログラムをC++で作成する方法について解説します。

フラット化とは、第1レベルのノードをすべて先に並べ、その後に第2レベルのノードが続くように、階層構造を持つリストを1本の直線的な連結リストへ変換する操作のことです。

マルチレベル連結リストとは

マルチレベル連結リストとは、多次元的なデータ構造の一種です。各ノードは2つのポインタを持ちます。1つは次のノードを指す「next」ポインタ、もう1つは1つ以上のノードからなる子リストを指す「child」ポインタです。この子ポインタは、他のリストのノードを指す場合もあれば、何も指さない（NULLである）場合もあります。

具体例で問題を理解しよう

以下のような入力を考えてみます。

入力：

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

出力：

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

ご覧のとおり、フラット化後のリストでは、まず第1レベルのノード（1, 9, 8, 4, 6）がすべて並び、その後に各ノードの子リストに属していたノード（7, 2, 3, 5）が続いています。

解決アプローチ

この問題に対するシンプルな解法は、幅優先探索（レベル順走査）に似たアルゴリズムを用いることです。

手順は以下のとおりです。

1. リストの先頭ノードから走査を開始し、同じレベルのノードを順にたどります。
2. あるノードにchildポインタが存在する場合、その子リストをテールポインタを使って現在のリストの末尾に接続します。
3. 接続後、新しく追加された部分の末尾までtailを更新します。
4. curポインタを進めながら、curがtailに到達するまで同じ処理を繰り返します。

この方法なら、再帰呼び出しを明示的に使わずとも、反復処理だけで効率よくフラット化できます。計算量はO(N)（Nは全ノード数）、追加のメモリ使用量はO(1)です。

C++での実装例

以下は、上記のロジックを実装したサンプルプログラムです。

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

#define SIZE(arr) (sizeof(arr)/sizeof(arr[0]))

class Node {
public:
    int data;
    Node *next;
    Node *child;
};

// 配列から連結リストを作成する関数
Node *createList(int *arr, int n) {
    Node *head = NULL;
    Node *p;
    for (int i = 0; i < n; ++i) {
        if (head == NULL)
            head = p = new Node();
        else {
            p->next = new Node();
            p = p->next;
        }
        p->data = arr[i];
        p->next = p->child = NULL;
    }
    return head;
}

// マルチレベル連結リストを構築する関数
Node *createList(void) {
    int arr1[] = {1, 9, 8, 4, 6};
    int arr2[] = {7, 3, 2};
    int arr3[] = {5};
    Node *head1 = createList(arr1, SIZE(arr1));
    Node *head2 = createList(arr2, SIZE(arr2));
    Node *head3 = createList(arr3, SIZE(arr3));
    head1->child = head2;          // ノード1の子リスト
    head1->next->child = head3;   // ノード9の子リスト
    return head1;
}

// リストをフラット化する関数
void flattenLinkedList(Node *head) {
    if (head == NULL)
        return;
    Node *tmp;
    Node *tail = head;
    // 現在の末尾を見つける
    while (tail->next != NULL)
        tail = tail->next;
    Node *cur = head;
    while (cur != tail) {
        if (cur->child) {
            // 子リストを末尾に接続
            tail->next = cur->child;
            tmp = cur->child;
            while (tmp->next)
                tmp = tmp->next;
            tail = tmp; // 新しい末尾を更新
        }
        cur = cur->next;
    }
}

int main(void) {
    Node *head = NULL;
    head = createList();
    flattenLinkedList(head);
    cout << "The flattened Linked List is ";
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    return 0;
}

実行結果

The flattened Linked List is 1 9 8 4 6 7 3 2 5

まとめ

マルチレベル連結リストのフラット化は、テールポインタを活用して子リストを順次末尾に接続していくことで、シンプルかつ効率的に実現できます。ポイントは以下の3点です。

• 各ノードのchildポインタを確認し、存在すればリスト末尾に接続する
• 接続のたびにtailポインタを新しい末尾へ更新する
• curがtailに到達した時点で処理を終了する

この手法は時間計算量O(N)、空間計算量O(1)で動作するため、大規模なデータにも対応できる実用的なアプローチです。ぜひ実際にコードを動かして、挙動を確認してみてください。