連結リストで表された数値に1を加えるアルゴリズムを解説

連結リストによる数値の表現とは

連結リストで数値を表現する場合、リストの各ノードが数値の1桁に対応します。リストの先頭ノードが最上位の桁を、末尾ノードが最下位の桁を保持する構造になっています。例えば、数値「202345」は連結リストでは (2→0→2→3→4→5) のように表されます。

このように表現された数値に1を加えるには、まず最下位の桁の値を確認します。その値が9未満であれば単純に1を足すだけで済みますが、9であった場合は繰り上がりが発生するため、一つ前の桁（上位の桁）の処理へと進む必要があります。

具体例

例として「1999」という数値を考えてみましょう。これは連結リストでは (1→9→9→9) と表されます。これに1を加えると、繰り上がりが連鎖して (2→0→0→0)、つまり「2000」になります。

入力：1999
出力：2000

アルゴリズムの手順

連結リストで表された数値に1を加えるには、以下の3つのステップに従います。

• 連結リストの反転： まず連結リストを反転します。これにより、最下位の桁が先頭に、最上位の桁が末尾に移動します。例えば 1→9→9→9 は 9→9→9→1 に変換されます。
• 1の加算と繰り上がりの処理： 反転後のリストを先頭から走査し、最初のノードに1を加算します。ノードの値が9であれば繰り上がりが発生するため、次のノードへ繰り上がりを伝播させます。繰り上がりがなくなるまでこの処理を繰り返します。
• リストを元に戻す： 最後に、リストを再度反転して元の順序に戻し、先頭ノード（ヘッド）を返して結果を出力します。

C++による実装例

以下は、上記のアルゴリズムをC++で実装したコード例です。

#include <iostream>
using namespace std;
// n=次のノード ; d=データ ; p=前のノード; h=先頭ノード; c=現在のノード
class Node {
    public:
        int d;
        Node* n;
};
Node *newNode(int d) {
    Node *new_node = new Node;
    new_node->d = d;
    new_node->n = NULL;
    return new_node;
}
Node *reverse(Node *h) {
    Node * p = NULL;
    Node * c = h;
    Node * n;
    while (c != NULL) {
        n = c->n;
        c->n = p;
        p = c;
        c = n;
    }
    return p;
}
Node *addOneUtil(Node *h) {
    Node* res = h;
    Node *temp, *p = NULL;
    int carry = 1, sum;
    while (h != NULL) {
        sum = carry + h->d;
        carry = (sum >= 10)? 1 : 0;
        sum = sum % 10;
        h->d = sum;
        temp = h;
        h = h->n;
    }
    if (carry > 0)
        temp->n = newNode(carry);
    return res;
}
Node* addOne(Node *h) {
    h = reverse(h);
    h = addOneUtil(h);
    return reverse(h);
}
int main() {
    Node *h = newNode(1);
    h->n = newNode(9);
    h->n->n = newNode(9);
    h->n->n->n = newNode(9);
    h = addOne(h);
    while (h != NULL) {
        cout << h->d;
        h = h->n;
    }
    cout<<endl;
    return 0;
}

コードのポイント

この実装では、reverse 関数がリストの反転を担当し、addOneUtil 関数が実際の加算と繰り上がりの処理を行います。繰り上がりが最後のノードまで伝播した場合（例：「999」に1を加える場合）、newNode を使って新しいノードを末尾に追加し、桁数が増えた数値にも正しく対応できるようになっています。

このアルゴリズムの計算量は、リストの反転と走査それぞれでリストの長さに比例するため、全体の時間計算量は O(n)、空間計算量は O(1) となります。