連結リストで表された2つの数値を加算する方法をC++で解説

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

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

このような形式の2つのリストが与えられたとき、それらを足し合わせて合計を求めるのが課題となります。ここでは、C++のSTLに含まれるstd::list（双方向連結リスト）を使用します。まず、処理の流れをつかむためにアルゴリズムから見ていきましょう。

アルゴリズム

addListNumbers(l1, l2)

Begin
    短い方のリストの先頭に0を追加し、l1とl2の桁数を揃える
    carry（繰り上がり） := 0
    res := 空のリスト
    l1の各ノードに対して以下を繰り返す
        item := (l1.item + l2.item + carry) mod 10
        res の先頭に item を挿入する
        carry := (l1.item + l2.item + carry) / 10
    繰り返し終了
    もし carry が 0 でなければ
        res の先頭に carry を追加する
    end if
    return res
End

C++による実装例

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

// 桁数の少ない方の先頭に0を追加し、両リストの長さを揃える
list<int> addListNumbers(list<int> l1, list<int> l2){
    if(l1.size() > l2.size()){
        for(int i = l2.size(); i != l1.size(); i++){
            l2.push_front(0);
        }
    }else if(l1.size() < l2.size()){
        for(int i = l1.size(); i != l2.size(); i++){
            l1.push_front(0);
        }
    }
    list<int>::reverse_iterator it1 = l1.rbegin();
    list<int>::reverse_iterator it2 = l2.rbegin();
    list<int> result;
    int carry = 0;
    while(it1 != l1.rend()){
        result.push_front((*it1 + *it2 + carry) % 10);
        carry = (*it1 + *it2 + carry) / 10;
        it1++; it2++;
    }
    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 = 512;
    int n2 = 14578;
    list<int> n1_list = numToList(n1);
    list<int> n2_list = numToList(n2);
    list<int> res = addListNumbers(n1_list, n2_list);
    cout << "First number: "; displayListNum(n1_list);
    cout << "Second number: "; displayListNum(n2_list);
    cout << "Result: "; displayListNum(res);
}

実行結果

First number: 512
Second number: 14578
Result: 15090

アルゴリズムのポイント

この実装の重要なポイントを整理すると、以下の4点になります。

• 桁数の調整： 加算を単純化するため、短い方のリストの先頭に0を追加して両者の桁数を揃えます。
• 逆イテレータの活用： rbegin()とrend()を使ってリストを後ろから走査することで、一の位から順に加算できます。
• 繰り上がり処理： 各桁の合計が10以上になった場合は、商をcarryに記録し、次の桁の計算に反映させます。
• 最終的な繰り上がり： すべての桁を処理した後もcarryが残っている場合は、結果の先頭に追加します。

計算量はO(max(m, n))です。ここでmとnはそれぞれのリストの長さを表します。筆算と同じ考え方をデータ構造上で実現するシンプルな手法なので、連結リストの操作に慣れる練習問題としても最適です。