C++で連結リストの2つの数を加算する方法(Add Two Numbers II)

問題の概要

2つの空でない連結リストが与えられ、それぞれが非負の整数を表しているとします。最上位の桁がリストの先頭に配置されており、各ノードには1桁の数字が格納されています。この2つの数を加算し、その結果を連結リストとして返す必要があります。

例えば、リスト [7, 2, 4, 3] と [5, 6, 4] を加算すると、結果は [7, 8, 0, 7] になります。

解法のアプローチ

最上位の桁が先頭にあるため、下位の桁から順に足し算を行う必要があります。しかし、連結リストは後方のノードへ直接アクセスするのが苦手です。そこで、スタックのLIFO(後入れ先出し)の性質を活用します。各リストのノードをあらかじめスタックにプッシュしておけば、ポップする順序で下位の桁から値を取り出すことができます。

アルゴリズムの手順

1. 値0を持つダミーノード(dummy)を作成し、スタックs1とs2を用意します。
2. l1の各ノードをs1に、l2の各ノードをs2にプッシュします。
3. 繰り上がりを管理する変数sumを0で初期化します。
4. s1またはs2が空でない間、以下の処理を繰り返します。
   • s1が空でなければ、sumにs1のトップの値を加算し、ポップします。
   • s2が空でなければ、sumにs2のトップの値を加算し、ポップします。
   • dummyの値を「sum % 10」に設定します。
   • 値「sum / 10」を持つ新しいノードを作成し、そのnextをdummyに接続します。
   • dummyを新しいノードに更新し、sumを「sum / 10」に更新します。
5. ループ終了後、dummyの値が0であればdummyのnextを返し、そうでなければdummyをそのまま返します。

C++での実装例

以下の実装例を見て、処理の流れをより深く理解しましょう。

#include <bits/stdc++.h>
using namespace std;
class ListNode{
   public:
   int val;
   ListNode *next;
   ListNode(int data){
      val = data;
      next = NULL;
   }
};
ListNode *make_list(vector<int> v){
   ListNode *head = new ListNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      ListNode *ptr = head;
      while(ptr->next != NULL){
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return head;
}
void print_list(ListNode *head){
   ListNode *ptr = head;
   cout << "[";
   while(ptr){
      cout << ptr->val << ", ";
      ptr = ptr->next;
   }
   cout << "]" << endl;
}
class Solution {
   public:
   ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
      ListNode* dummy;
      dummy = new ListNode(0);
      stack <ListNode*> s1, s2;
      while(l1){
         s1.push(l1);
         l1 = l1->next;
      }
      while(l2){
         s2.push(l2);
         l2 = l2->next;
      }
      int sum = 0;
      while(!s1.empty() || !s2.empty()){
         if(!s1.empty()){
            sum += s1.top()->val;
            s1.pop();
         }
         if(!s2.empty()){
            sum += s2.top()->val;
            s2.pop();
         }
         dummy->val = (sum % 10);
         ListNode* newNode = new ListNode(sum / 10);
         newNode->next = dummy;
         dummy = newNode;
         sum /= 10;
      }
      return dummy->val == 0? dummy->next : dummy;
   }
};
main(){
   vector<int> v1 = {7,2,4,3};
   ListNode *h1 = make_list(v1);
   vector<int> v2 = {5,6,4};
   ListNode *h2 = make_list(v2);
   Solution ob;
   print_list(ob.addTwoNumbers(h1, h2));
}

入力

[7,2,4,3]
[5,6,4]

出力

[7, 8, 0, 7]

計算量の分析

• 時間計算量: O(max(m, n)) — mとnはそれぞれの連結リストの長さです。各ノードを一度ずつ処理するため、リストの長い方に比例します。
• 空間計算量: O(m + n) — すべてのノードを2つのスタックに格納するために必要となります。

このようにスタックを活用することで、連結リストを逆順に走査せずとも、下位の桁から順に加算処理を行うことができ、繰り上がりも正しく管理できます。