C++で不変リンクリストを逆順に出力する方法

問題の概要

不変（イミュータブル）なリンクリストが与えられたとき、各ノードの値を逆順にすべて出力することを考えます。この問題を解くためには、以下のインターフェースを使用します。

• ImmutableListNode ― 不変リンクリストのインターフェースであり、リストの先頭ノード（head）が与えられます。

リンクリストへアクセスするために、次の2つの関数が利用できます。

• ImmutableListNode.printValue() ― 現在のノードの値を出力します。
• ImmutableListNode.getNext() ― 次のノードを返します。

たとえば、リストが [0, -4, -1, 3, -5] の場合、出力は [-5, 3, -1, -4, 0] となります。

解法のアプローチ

リンクリストは不変（イミュータブル）であるため、ノードのポインタを書き換えて逆順にすることはできません。そこで、スタックのLIFO（後入れ先出し）の性質を利用します。ノードを順番にスタックへ格納し、その後スタックから取り出しながら値を出力すれば、自然と逆順になります。

アルゴリズムの手順

• ImmutableListNode 型のノードを格納するスタック st を定義します。
• head が null でない間、以下を繰り返します。
  • head をスタック st にプッシュします。
  • head を次のノード（getNext() の結果）に更新します。
• スタックが空でない間、以下を繰り返します。
  • スタックの先頭ノードの値を出力します。
  • スタックからノードを取り除きます（ポップ）。

C++での実装例

以下の実装を見ると、理解がより深まるでしょう。

class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        stack <ImmutableListNode*> st;
        while(head){
            st.push(head);
            head = head->getNext();
        }
        while(!st.empty()){
            st.top()->printValue();
            st.pop();
        }
    }
};

入力例

[0,-4,-1,3,-5]

出力例

[-5,3,-1,-4,0]

計算量の分析

• 時間計算量： O(n) ― 各ノードを1回ずつスタックにプッシュし、1回ずつポップするため、リストの長さ n に対して線形時間で処理が完了します。
• 空間計算量： O(n) ― すべてのノードを一時的にスタックに保持するため、追加のメモリが必要です。

なお、再帰を用いて同様の結果を得ることも可能ですが、リストが長い場合にはスタックオーバーフローのリスクがあるため、明示的なスタックを使うこの方法が安全です。