アルゴリズム1000本ノック（８）: Add 2 numbers

Problem

問題は LeetCode より拝借しています.

正の整数を保持する２つの単方向リストが与えられた時, 各要素を１つの桁のように考えて
２つのリストの合計値を保持するリストを返却せよ. 次の要素への桁上りも考慮すること.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution

整数同士の足し算の筆算を行うようなイメージです. （見た目的には低い位と高い位の順番が逆ですが） ２つのリストの先頭から開始して, 合計値を求め, 10以上の場合は次の要素の計算に1を持ち越していく繰り返しです. 先に片方のリストが空になった場合は一方の値だけを合計値として扱います. 両方のリストが空になった時点で計算は終了です.

最後の計算結果が10以上であった場合には, 最後に1を持ち越しておくことをお忘れなく.

Java code:

Nを２つのリストの内長い方の長さだとして, 計算量・空間量ともにO(N)となります. ただし空間量に関しては, 今回のプログラムでは結果の格納に新しい単方向リストを用意していますが, 実際には片方のリストを上書きしていく形でも実行結果に影響は及ぼしません. この場合は余分な空間量は消費しないことになります.