2. Add Two Numbers (Medium)

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

2つの数値が連結リストの形で渡されるので、その和を求める問題。
ただしリストは逆順で格納されていて(802なら2 -> 0 -> 8のように)、結果も同じく逆順をリストでつないで返す。

回答

# Definition for singly-linked list.  
# class ListNode  
#     attr_accessor :val, :next  
#     def initialize(val)  
#         @val = val  
#         @next = nil  
#     end  
# end  

# @param {ListNode} l1  
# @param {ListNode} l2  
# @return {ListNode}  

class ListNode  
    def to_i  
        array = []  
        array.push(self.val)  
        ln = self  
        while ln.next  
            ln = ln.next  
            array.push(ln.val)  
        end  

        array.reverse.join.to_i  
    end  
end  

def add_two_numbers(l1, l2)  
    dummyHead = ListNode.new(0)  
    current = dummyHead  
    (l1.to_i + l2.to_i).to_s.chars.reverse.each do |c|  
        current.next = ListNode.new(c.to_i)  
        current = current.next  
    end  
    dummyHead.next  
end

正攻法は繰り上がりを考慮しつつ順番に足し上げていく方法だと思うけど、面倒だったのでリストから元の数字を返すメソッドto_iを定義して、足し算はRubyに任せることにした。
和を求めたら、あとは逆に数字からリストを生成すればよい。

実はさっき見直すまでリストの生成をちゃんとやってなくて、でもAcceptされてしまっていたので、生成部分はSolutionを参考にした。先頭にダミーノードを作っておくとシンプルにできるようだ。

正攻法での回答

def add_two_numbers(l1, l2)  
    dummyHead = ListNode.new(0)  
    p = l1  
    q = l2  
    current = dummyHead  
    carry = 0  
    while (p != nil || q != nil)  
        x = (p != nil) ? p.val : 0  
        y = (q != nil) ? q.val : 0  
        sum = carry + x + y  
        carry = sum / 10  
        current.next = ListNode.new(sum % 10)  
        current = current.next  
        p = p.next if p != nil  
        q = q.next if q != nil  
    end  

    if carry > 0  
        current.next = ListNode.new(carry)  
    end  

    dummyHead.next  
end

Solutionを参考に、足し算と繰り上がりを実装するとこうなる。
実行時間や消費メモリはほぼ変わりがなかった。