Zenn
🐇

JavaScriptで解く！『LeetCode Arai 60』#2 Add Two Numbers

2024/12/27に公開
JavaScript
LeetCode
tech

このシリーズでは、LeetCode で良問として知られている Arai 60 を、JavaScript を用いて順番に解説していきます。

第2問となる「Add Two Numbers」は、単一連結リストというデータ構造を扱いながら、再帰処理の基本を学ぶことができる良問です。

ぜひ、この記事を参考にしながら取り組んでみてください！

第2問「Add Two Numbers」について

問題へのアクセス

Add Two Numbers 問題ページ（LeetCode）

問題概要

問題
2つの非負整数を、「各桁の数字」を逆順に並べた形で 単一連結リスト（以下、リスト と表記）で受け取り、2つのリストが表す整数の合計を同じ形式の リスト で返せ。

具体例として、

l1: 2 -> 4 -> 3   （整数 342）
l2: 5 -> 6 -> 4   （整数 465）

それぞれを逆順で表しているので、342 + 465 = 807 という計算結果を

newList: 7 -> 0 -> 8

と逆順でリストにして返します。

前提知識：単一連結リスト (Singly Linked List)

単一連結リストとは？

単一連結リストは、各ノード (Node) が値と次のノードへの ポインタ (next) を持ち、一方向 にのみ辿っていけるデータ構造です。

[head] -> [val=2, next] -> [val=4, next] -> [val=3, next=null]
  1. 先頭ノード (head) から順番に辿っていく
  2. 途中を飛び越えることはできない（配列のように添字指定で即座にアクセスするのは苦手）
  3. ノードの挿入・削除が比較的容易

「Add Two Numbers」のような桁の計算問題では、桁のつながりをリストで管理でき、次の桁の計算がシンプルになるという利点があります。

コード全体

今回の実装例はこちらです。

/**
 * 単一連結リストの定義
 * LeetCode の実行環境で事前に定義されているので、
 * こちらをインスタンス化したものを return する
 * function ListNode(val, next) {
 *     this.val = (val === undefined ? 0 : val);
 *     this.next = (next === undefined ? null : next);
 * }
 */
var addTwoNumbers = function(l1, l2, carry = 0) {
    // ベースケース: l1、l2、carry の全てが存在しない場合、計算終了
    if (!l1 && !l2 && carry === 0) {
        return null;
    }

    // 現在の桁の値を取得
    const val1 = l1 ? l1.val : 0;
    const val2 = l2 ? l2.val : 0;
    const sum = val1 + val2 + carry;

    // 新しいノードを作成し、次の桁の計算を再帰的に行う
    const newNode = new ListNode(sum % 10);
    newNode.next = addTwoNumbers(
        l1 ? l1.next : null,
        l2 ? l2.next : null,
        Math.floor(sum / 10)
    );

    return newNode;
}

実装方針

  1. 各桁の合計 + 繰り上がり (carry) を求める

    • l1.val、l2.val、そして前の桁からの繰り上がり値 carry を足し合わせる。
    • 例： sum = 2 + 5 + 0 = 7

  2. 合計を10で割った余りが、 新しいノードの値になる

    • sum % 10 → 新しいノードに格納される 1桁の値
    • 例： sum = 7 のとき、新しいノードの値は 7

  3. 合計を10で割った商が、 次の桁の計算で使う繰り上がり carry になる

    • Math.floor(sum / 10)
    • 例： sum = 7 のとき、繰り上がり carry は 0
    • sum = 12 のとき、繰り上がり carry は 1

  4. 次の桁の計算へ進む

    • l1.next、l2.next を使って 再帰的 に次のノードを計算していく。
    • 新しいノード (newNode) の next が、次桁の計算結果を受け取る形。

  5. すべてのノードを計算し終え、繰り上がりもないときに再帰終了

    • l1, l2, carry すべてが存在しない場合は null を返す。

再帰処理が有効な理由

1. 再帰的アプローチとは？

ある関数の処理の中で 自分自身の関数を呼び出す アプローチを「再帰的アプローチ」と呼びます。
今回の場合、

newNode.next = addTwoNumbers(/* 次の桁情報 */);

という形で、 1桁分の処理が終わったら次の桁へと同じ処理を委ねる ことで、シンプルにコードを記述できます。

2. リスト構造との相性

ノードが一方向に順番に並んでいるだけであり、「次のノードへ進む → また同じ処理」 という流れと再帰が非常に合致します。
ループ (while や for) で実装する場合ももちろん可能ですが、コードがネストしにくい 再帰の方が読みやすいことも多いです。

処理をトレースしてみる

実際に、以下のリスト同士を加算するとしましょう。

l1 = 2 -> 4 -> 3   （整数 342）
l2 = 5 -> 6 -> 4   （整数 465）

1. 第1回目の呼び出し

  • carry = 0 初期値
  • val1 = 2, val2 = 5
  • sum = 2 + 5 + 0 = 7
  • 新しいノードの値 newNode.val = 7
  • carry = Math.floor(7 / 10) = 0
  • 次の呼び出しは addTwoNumbers(l1.next, l2.next, 0) → ( l1.next = 4, l2.next = 6 )

2. 第2回目の呼び出し

  • val1 = 4, val2 = 6, carry = 0
  • sum = 4 + 6 + 0 = 10
  • 新しいノードの値 newNode.val = 10 % 10 = 0
  • carry = Math.floor(10 / 10) = 1
  • 次の呼び出しは addTwoNumbers(l1.next, l2.next, 1) → ( l1.next = 3, l2.next = 4 )

3. 第3回目の呼び出し

  • val1 = 3, val2 = 4, carry = 1
  • sum = 3 + 4 + 1 = 8
  • 新しいノードの値 newNode.val = 8
  • carry = Math.floor(8 / 10) = 0
  • 次の呼び出しは addTwoNumbers(l1.next, l2.next, 0) → ( l1.next = null, l2.next = null )

4. 第4回目の呼び出し

  • ここで l1、l2 ともに null、 さらに carry = 0
  • if (!l1 && !l2 && carry === 0) { return null; }
  • つまり、これ以上の桁はないので再帰終了

5. 結果

最初に生成されたノードから順に見ていくと、

7 -> 0 -> 8

となり、これは逆順表示で 807 を表すので、342 + 465 = 807 の答えとなります。

計算量の目安

  • 時間計算量: O(n)
    • n を l1、l2 のうち長い方のリストのノード数とすると、最大 n + 1 回の再帰呼び出しが起きるため O(n)。
  • 空間計算量: O(n)
    • 結果のリストのノード数も最大で n + 1 個（繰り上がりが1つ余分に増えるケース）になる可能性があるため、リストとしても O(n)。
    • 再帰呼び出しによるコールスタックも O(n) ですが、一般的にはリストサイズがそれほど大きくないケースが多いため、ここでは大きな問題にならないことが多いです。

まとめ

  1. 単一連結リスト は、ノードのつながりを一方向に持つシンプルな構造。
  2. 各桁の合計と繰り上がり (carry) を再帰で計算 することで、処理をシンプルに記述できる。
  3. 再帰は「次のノードへ進む → 同じ処理」の繰り返し と非常に相性が良い。
  4. ベースケース (再帰終了条件) は「すべてのノードと carry がなくなるタイミング」 で判定する。

再帰的アプローチは、最初は馴染みにくいかもしれませんが、リストの構造 と 分割して考える という考え方の学習に非常に有効です。
ぜひ、今回の方法をマスターして、より複雑なリスト操作に挑戦してみてください！

以上で、第2問「Add Two Numbers」 の解説は終了です。

次回以降も、Arai 60 の他の問題を JavaScript で解説していきますので、お楽しみに！

Discussion