C++で2次元行列から2Dリンクリストを作成する方法（反復アプローチ）

1つの2次元行列が与えられたとき、反復アプローチを使ってそれを2Dリンクリストに変換する方法を解説します。変換後のリンクリストでは、各ノードが右方向へのポインタ（right）と下方向へのポインタ（down）を持つ構造になります。

例として、次のような入力行列を考えてみましょう。

この場合、出力は各行・各列がポインタで連結された2Dリンクリストになります。

アルゴリズムの手順

この問題は、以下の手順で解くことができます。

• real_head を NULL で初期化します。

• サイズ m の配列 head_arr を定義し、各行の先頭ノードを保持できるようにします。

• i を 0 から m 未満まで1ずつ増やしながら、以下を繰り返します。

  • head_arr[i] を NULL で初期化します。

  • j を 0 から n 未満まで1ずつ増やしながら、以下を繰り返します。

    • 値 mat[i][j] を持つ新しいノード p を作成します。

    • real_head が NULL の場合、real_head := p とします。

    • head_arr[i] が NULL の場合、head_arr[i] := p とします。

    • そうでなければ、right_ptr の right ポインタに p を接続します。

    • right_ptr := p と更新します。

• i を 0 から m - 1 未満まで1ずつ増やしながら、以下を繰り返して行同士を縦方向に連結します。

  • p := head_arr[i]、q := head_arr[i + 1] とします。

  • p と q がどちらも NULL でない間、以下を繰り返します。

    • p の down ポインタに q を設定します。

    • p := p の right、q := q の right と更新します。

• 最後に real_head を返します。

実装例

理解を深めるために、以下のC++での実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int data;
   TreeNode *right, *down;
   TreeNode(int d){
      data = d;
      right = down = NULL;
   }
};
void show_2d_list(TreeNode* head) {
   TreeNode *right_ptr, *down_ptr = head;
   while (down_ptr) {
      right_ptr = down_ptr;
      while (right_ptr) {
         cout << right_ptr->data << " ";
         right_ptr = right_ptr->right;
      }
      cout << endl;
      down_ptr = down_ptr->down;
   }
}
TreeNode* make_2d_list(int mat[][3], int m, int n) {
   TreeNode* real_head = NULL;
   TreeNode* head_arr[m];
   TreeNode *right_ptr, *p;
   for (int i = 0; i < m; i++) {
      head_arr[i] = NULL;
      for (int j = 0; j < n; j++) {
         p = new TreeNode(mat[i][j]);
         if (!real_head)
            real_head = p;
         if (!head_arr[i])
            head_arr[i] = p;
         else
            right_ptr->right = p;
         right_ptr = p;
      }
   }
   for (int i = 0; i < m - 1; i++) {
      TreeNode *p = head_arr[i], *q = head_arr[i + 1];
      while (p && q) {
         p->down = q;
         p = p->right;
         q = q->right;
      }
   }
   return real_head;
}
int main() {
   int m = 3, n = 3;
   int mat[][3] = {
      { 10, 20, 30 },
      { 40, 50, 60 },
      { 70, 80, 90 } };
   TreeNode* head = make_2d_list(mat, m, n);
   show_2d_list(head);
}

入力

{ { 10, 20, 30 },
{ 40, 50, 60 },
{ 70, 80, 90 } }

出力

10 20 30
40 50 60
70 80 90

処理のポイント

このアルゴリズムのポイントは、大きく分けて2段階あることです。

1. 横方向の連結： 各行を走査しながらノードを作成し、right ポインタで同じ行内のノード同士をつなぎます。head_arr 配列に各行の先頭ノードを記録しておくのが重要です。
2. 縦方向の連結： 隣り合う行の先頭ノード同士から順に、down ポインタで対応する位置のノードをつなげていきます。

計算量は行列の全要素を一度ずつ処理するため O(m × n) となり、非常に効率的です。再帰を使わない反復処理なので、大きな行列でもスタックオーバーフローの心配なく安全に動作します。