LeetCode 2. Add Two Numbers

LeetCode 2問目

1問目はこれ modalsoul.hatenablog.com

2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

負でない整数2つを表すリンクリストが2つ与えられる

このリストは、それぞれのノードに整数の各桁が逆順に格納されている

この整数の和を求め、リンクリストとして返却する

Examples

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

コードその１

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
        def calc(l:ListNode):Int = {
            var result = 0L
            var hasNext = true
            var c = l
            var digit = 1
            while(hasNext) {
                result = c.x * digit + result
                if(c.next == null) hasNext = false
                c = c.next
                digit = digit * 10
            }
            result
        }
        var sum = calc(l1) + calc(l2)
        var head = new ListNode(_x = sum%10)
        var prev:ListNode = head
        sum = sum/10
        while(sum > 0) {
            val next = new ListNode(_x = sum%10)
            prev.next = next
            prev = next
            sum = sum/10
        }
        head
    }
}

考えたこと

• リンクリストを数値に戻し、足し算する
• 足し算の結果をリンクリストへ変換する

---

これだとExampleのようなケースでは動くけど、リンクリストの長さが増えると動かない

コードその２

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
        def run(a:ListNode, b:ListNode, acc:ListNode = null, prev:ListNode = null, carried:Boolean = false): ListNode = {
          if(a == null && b == null) {
            if (carried) prev.next = new ListNode(_x = 1)
            acc
          }
          else {
            val x = (if(a != null) a.x else 0) + (if(b != null) b.x else 0) + (if(carried) 1 else 0)
            val node = new ListNode(_x = x%10)
            if(acc == null) {
              run(a.next, b.next, acc = node, prev = node, x > 9)
            }
            else {
              prev.next = node
              run(if(a == null) null else a.next, if(b == null) null else b.next, acc = acc, prev = node, x > 9)
            }
          }
        }
        run(l1, l2)
    }
}

考えたこと

• リンクリストを辿る時点でその桁の足し算をしてしまう
• 桁の繰り上がり有る無しを持ち回す

---

こっちはすべてのテストケースをパスした

Runtime: 380 ms, faster than 99.59% of Scala online submissions for Add Two Numbers. Memory Usage: 58.2 MB, less than 78.57% of Scala online submissions for Add Two Numbers.