C++で連結リスト表現の整数に1を加算する方法

問題の概要

負でない整数が、各桁の数字を要素とする空でない単方向連結リストとして表現されているとします。ここでの課題は、その整数に1を加算することです。整数には余計な先行ゼロが含まれていない(数値0そのものを除く)ものとみなせるものとし、連結リストでは最上位の桁が先頭ノード(head)に格納されています。

例えば、入力が [1,2,3] の場合、出力は [1,2,4] になります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

1. head が NULL の場合は、head をそのまま返します。
2. curr = head、req = NULL として初期化します。
3. curr が NULL になるまで次の処理を繰り返します。
   • curr の値(val)が 9 以外であれば、req := curr と更新します。
   • curr を次のノード(curr→next)に進めます。
4. req が NULL のまま(=すべての桁が9だった)の場合は、以下を行います。
   • 値が 1 の新しいノード dummy を作成します。
   • dummy の next に head を設定します。
   • head が NULL になるまで、すべてのノードの値を 0 に書き換えます。
   • dummy を返します。
5. それ以外の場合は、以下を行います。
   • req の値を 1 増やします。
   • req を次のノードに進め、残りのノード(9が並んでいた部分)の値をすべて 0 にします。
   • head を返します。

アルゴリズムのポイント

このアルゴリズムの核心は、「最後に現れた9以外の桁」を見つけることにあります。繰り上がりが発生するのは、末尾が9で構成されている部分だけだからです。変数 req は「9以外の最後のノード」を指しており、そこで +1 を行い、それ以降の9をすべて0に置き換えるだけで答えが得られます。全桁が9のケースのみ桁数が1つ増えるため、先頭に新しいノードを追加します。時間計算量は O(n)、追加で必要な空間は最小限(全桁9の場合も新ノード1個のみ)と非常に効率的です。

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* plusOne(ListNode* head) {
      if (!head)
         return head;
      ListNode* curr = head;
      ListNode* req = NULL;
      while (curr) {
         if (curr->val != 9) {
            req = curr;
         }
         curr = curr->next;
      }
      if (!req) {
         ListNode* dummy = new ListNode(1);
         dummy->next = head;
         while (head) {
            head->val = 0;
            head = head->next;
         }
         return dummy;
      }
      else {
         req->val++;
         req = req->next;
         while (req) {
            req->val = 0;
            req = req->next;
         }
         return head;
      }
   }
};
main(){
   Solution ob;
   vector<int> v = {1,4,5};
   ListNode *head = make_list(v);
   print_list(ob.plusOne(head));
}

入力

{1,4,5}

出力

[1, 4, 6]

まとめ

連結リストで表現された整数への1の加算は、「最後の9以外の桁」を記録しておくことで、リストを反転させたり再帰を使ったりせずに、一度の走査で解くことができます。繰り上がりのパターンを整理して理解すれば、技術面接でも役立つ定番問題ですので、ぜひマスターしておきましょう。