繰り
数の
海外で定番の問題リスト 4 本には入っていません
問題
0 以上のhead1 と head2 を
- 1 つの
節が 1 つの 桁 (0 から 9) を 持ちます。 先頭が 1 の位で、 次が 10 の 位、 その 次が 100 の 位、と 並びます。 たとえば 352 は [2, 5, 3]です - 数が 0 の
ときは [0]です。それ以外で、 いちばん上の 桁 (リストの 最後 ) が 0 に なる ことは ありません - 答えも
同じ形で、 先頭を 1 の 位に して返します - 各節は
val(値) とnext(次の節) を 持ちます。 最後の 節の nextは、Python では None、JavaScript では null、Go では nilです。Go の 節は ListNodeで、Val、Nextと大文字で 始まります - それぞれの
節の 数は 1 以上 100 以下です。 桁が 100 あるので、 言語の 整数に 直して 足す ことは できません
例では、
入力と出力の例
例 1
352 と 471 を
例 2
9999 と 1 を
例 3
0 と 0 を
面接での聞かれ方
連結リストの
- 「桁を
逆順に 持つ 2 本の 連結リストの 和を、 同じ形で 返してください」 - 「整数に
直して 足して、 リストに 戻せば よいのでは？」という 答えには、 「桁が 100 あったら？」と 返されます。 言語に よっては溢れます - 書き終えた
あとに 「桁が 上の 位から 並んでいたら どうしますか？」と 続きを 聞かれる ことがあります。 その ときは 両方を 逆に してから 足すか、 スタックに 積んで 後ろから足します
ミドルの
ヒント
まだ開いていません
付箋は 4 枚。下の段ほど答えに近づきます
ヒント 2
ヒント 3
ヒント 4答えに近い
アルゴリズムのチートシートの「配列と文字列」に、
関わる学び
配列と
まず
段 1
まずは
段 2
先頭が 1 のcarry を
段 3
片方が
段 4
答えのdummy のdummy.next を
解答
Python
Python
def add_digit_lists(
head1, head2
):
dummy = ListNode(0)
tail = dummy
a, b = head1, head2
carry = 0
while a or b or carry:
s = carry
if a:
s += a.val
a = a.next
if b:
s += b.val
b = b.next
carry = s // 10
node = ListNode(s % 10)
tail.next = node
tail = tail.next
return dummy.nextJavaScript
JavaScript
function addDigitLists(
head1, head2
) {
const dummy = new ListNode(0);
let tail = dummy;
let a = head1;
let b = head2;
let carry = 0;
while (a !== null
|| b !== null
|| carry !== 0) {
let s = carry;
if (a !== null) {
s += a.val;
a = a.next;
}
if (b !== null) {
s += b.val;
b = b.next;
}
carry = Math.floor(s / 10);
tail.next = new ListNode(
s % 10
);
tail = tail.next;
}
return dummy.next;
}Go
Go
func addDigitLists(
head1, head2 *ListNode,
) *ListNode {
dummy := &ListNode{}
tail := dummy
a, b := head1, head2
carry := 0
for a != nil || b != nil ||
carry != 0 {
s := carry
if a != nil {
s += a.Val
a = a.Next
}
if b != nil {
s += b.Val
b = b.Next
}
carry = s / 10
tail.Next = &ListNode{
Val: s % 10,
}
tail = tail.Next
}
return dummy.Next
}1 つの
計算量
- 時間は O(max(m, n)) です。
m と n は 2 本の 節の 数で、 長い方の 分だけ、 最後の 繰り 上がりが あれば 1 つ 多く回ります - 答えの
リストに O(max(m, n)) の 節を 作ります。 それ以外の 記憶は O(1) です
よく
- 最後の
繰り 上がりを忘れる。 繰り返しの 条件を 「どちらかに 節が 残っている」だけに すると、 例 2 で 最後の 1 が 消え、 0、 0、 0、 0 になります - 短い方が
尽きた ところで止める。 例 2 で 1 の 位だけ足して 終えると、 残りの 9、 9、 9 が 抜けます。 尽きた側は 0 として 足し続けます - 整数に
直して足す。 JavaScript の 数は 2 の 53 乗あたりから 正しく 表せず、 Go の int も 19 桁ほどで 溢れます。 100 桁では 答えが崩れます - 答えを
上の 位から並べる。 この 問題の 答えは、 入力と 同じく 1 の 位が先頭です
解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日
面接での
書き始める
「先頭が 1 の
位なので、 2 本を 同時に 進めると 筆算と 同じ 順に なります。 その位の 2 つの 桁と 繰り 上がりを 足し、 10 で 割った 余りを 答えの 節に、 商を 次の 繰り 上がりにします。 どちらかに 節が 残るか 繰り 上がりが ある間は 回し、 尽きた側は 0 と 見ます。 時間は O(max(m, n)) です。」
書き終えたら、
「例 2 では、
1 の 位が 9 + 1 で 10、 0 を 書いて 1 を 繰り上げます。 10 の 位から 1000 の 位までは 9 と 繰り 上がり 1 で 10 なので、 0 を 書いて 1 を 繰り上げ続けます。 両方とも 尽きても 繰り 上がりが 1 残るので、 もう 1 回回って 1 を 書き、 0、 0、 0、 0、 1 です。」