LeetCode の Add Two Numbers を解いてみます。
問題の概要
- インプット(引数)
- 数値の1桁ごとの値を格納した連結リスト(ただし数字は逆順になっている)を2つ
- 例:
(2 -> 4 -> 3)
と (5 -> 6 -> 4)
(342と564の数値を逆順の連結リストで表したもの)
- アウトプット(戻り値)
- 与えられた連結リストが表す元の数値どうしを加算したものを連結リストに格納したもの(これも逆順にする)
- 例にあげた引数の場合、 342 + 465 = 807 なので
{7 -> 0 -> 8}
を返す必要がある
ちなみに連結リストのクラスは以下で定義されています
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
答え
解答のコード例としては以下になります。順に各桁を加算していくことになります。
最終的な答えを格納するためのダミーの連結リスト(ListNode)を用意しておきます。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1;
ListNode q = l2;
ListNode curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) {
p = p.next;
}
if (q != null) {
q = q.next;
}
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
}
以下のあたりの考慮が抜けないようにしないといけません
- 加算時の繰り上がり
- 引数の連結リストの長さは違うかもしれない(数値の桁数が異なるかもしれない)
- 1番最後の繰り上がり(数値の先頭桁での繰り上がり)
関連サイト
https://euro.qrunch.io/entries/Zu9MHIWO1O4bI4Hv