05. Add Two Numbers

読了目安約1分

Linked List / LeetCode 2 (Medium) — 逆順に格納された 2 つの数を、桁上がりに注意して足す。

この章の目次

問題

LeetCode 2. Add Two Numbers（Medium / カテゴリ: Linked List）

非負整数を表す 2 本の連結リスト l1、l2 が与えられます。各ノードは 1 桁の数字を持ち、数は逆順（1 の位が先頭）に格納されています。 2 つの数の和を、同じ逆順形式の連結リストで返してください。

考え方

ヒント 1

筆算の足し算と同じです。 1 の位が先頭にあるので、リストを先頭から順にたどりながら、対応する桁どうしと繰り上がりを足せます。

ヒント 2

2 本の長さは違ってよく、尽きた方の桁は 0 とみなします。両方が尽きても繰り上がりが残っていれば、もう 1 ノード作ります。

Swift 実装のポイント

結果のリストはダミーの先頭ノードから伸ばすと、先頭だけの場合分けが要りません。
ループ条件は p != nil || q != nil || carry > 0 の 3 条件です。
尽きた方の桁は p?.val ?? 0 で 0 に落とせます。桁は sum % 10、繰り上がりは sum / 10 です。

模範解答

Swift
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        let dummy = ListNode(0)
        var tail = dummy
        var p = l1
        var q = l2
        var carry = 0
        while p != nil || q != nil || carry > 0 {
            let sum = (p?.val ?? 0) + (q?.val ?? 0) + carry
            carry = sum / 10
            let node = ListNode(sum % 10)
            tail.next = node
            tail = node
            p = p?.next
            q = q?.next
        }
        return dummy.next
    }
}

計算量: O(max(m, n)) 時間、O(max(m, n)) 追加メモリ（答えのリスト分）。