LeetCode - Add Two Numbers

LeetCode の Add Two Numbers を解いてみます。

問題の概要

• インプット（引数）
  • 数値の１桁ごとの値を格納した連結リスト（ただし数字は逆順になっている）を２つ
    • 例：(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. 最終的な答えはnext以降に連結される
        ListNode dummyHead = new ListNode(0);
        
        ListNode p = l1;
        ListNode q = l2;
        
        ListNode curr = dummyHead;  // 現在の計算位置
        
        int carry = 0;  // 繰り上がり用の値
        
        // ２つのListNodeのどちらかの終端に来るまで繰り返す
        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;
            
            // 与えられたListNodeの長さは異なる場合もあるので、各々nullチェック必要
            if (p != null) {
                p = p.next;
            }
            if (q != null) {
                q = q.next;
            }
        }
        
        // 最終的に繰り上がっていたらそれも連結する
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        
        // ダミーのListNodeの先頭の0という値は意味がないので、next以降の連結リストを返す
        return dummyHead.next;
    }
}

以下のあたりの考慮が抜けないようにしないといけません

• 加算時の繰り上がり
• 引数の連結リストの長さは違うかもしれない（数値の桁数が異なるかもしれない）
• １番最後の繰り上がり（数値の先頭桁での繰り上がり）

---

関連サイト

https://euro.qrunch.io/entries/Zu9MHIWO1O4bI4Hv