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

本記事では、連結リスト（リンクリスト）に格納された数値に対して1を加算する方法について詳しく解説します。この手法では、数値の各桁が連結リストの各ノードに一つずつ格納されます。例えば、数値が512の場合、以下のように表現されます。

512 = (5)-->(1)-->(2)-->NULL

このリストをインクリメント関数に渡すと、1を加算した結果として新しいリストが返されます。ここでは、C++のSTL（Standard Template Library）が提供するlistコンテナを使用して実装します。まず、処理の流れを理解しやすくするために、アルゴリズムを見ていきましょう。

アルゴリズム

incrementList(l1)

Begin
    carry := 1
    res := 空のリスト
    l1 の各ノード n について、末尾から先頭へ向かって走査する:
        item := (l1.item + carry) mod 10
        item を res の先頭に挿入する
        carry := (l1.item + carry) / 10
    done
    もし carry が 0 でなければ、
        carry を res の先頭に追加する
    end if
    return res
End

実装のポイント

このアルゴリズムの核心は「繰り上がり（carry）」の処理です。最下位桁から順に各桁へ1を加算していき、その結果が10以上になった場合には繰り上がりを発生させます。逆イテレータ（reverse_iterator）を使うことで、リストを末尾から先頭方向へ効率的に走査できます。

特筆すべきケースとして、すべての桁が9である数値（例：9999）があります。この場合、加算によって新たな桁が追加されるため、ループ終了後にcarryが残っているかどうかを確認し、必要であれば新しい桁を先頭に挿入します。

C++による実装例

#include<iostream>
#include<list>
using namespace std;

// リストで表された数値に1を加算する関数
list<int> incListNum(list<int> l1){
    list<int>::reverse_iterator it1 = l1.rbegin();
    list<int> result;
    int carry = 1; // 加算する1
    while(it1 != l1.rend()){
        result.push_front((*it1 + carry) % 10);
        carry = (*it1 + carry) / 10;
        it1++;
    }
    if(carry != 0){
        result.push_front(carry); // 繰り上がりが残れば新しい桁を追加
    }
    return result;
}

// 整数をリスト形式に変換する補助関数
list<int> numToList(int n){
    list<int> numList;
    while(n != 0){
        numList.push_front(n % 10);
        n /= 10;
    }
    return numList;
}

// リストの内容を表示する補助関数
void displayListNum(list<int> numList){
    for(list<int>::iterator it = numList.begin(); it != numList.end();
    it++){
        cout<<*it;
    }
    cout << endl;
}

int main() {
    int n1 = 9999;
    list<int> n1_list = numToList(n1);
    list<int> res = incListNum(n1_list);
    cout << "The number: "; displayListNum(n1_list);
    cout << "Result: "; displayListNum(res);
}

実行結果

The number: 9999
Result: 10000

計算量と考察

このアルゴリズムの時間計算量はO(n)、空間計算量もO(n)となります（nはリストの長さ、つまり数値の桁数）。連結リストはランダムアクセスができないため、末尾から走査するために双方向連結リストの逆イテレータを活用しています。

なお、単方向連結リストしか使えない場合は、再帰を利用して末尾から処理を行うか、事前にリストを反転させてから順方向に走査するなどの工夫が必要になります。また、非常に大きな数値を扱う場合、この方式は整数型のオーバーフローを気にせず任意桁数の演算ができるという利点があります。