言語は Python3 でやってます。

問題

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

1 の桁・10 の桁、100 の桁・・・という形で各桁の数字がノードとなる LinkedList が 2 つ与えられるので、そのLinkedListが表している数字を合計して、LinkedListで返してね、という問題。

2つのLinkedListの最後のノードは0ではない。

解答①

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def addListNodeValues(l1, l2, num, ratio):
            if l1:
                num += l1.val * ratio
            if l2:
                num += l2.val * ratio
            if l1 or l2:
                return addListNodeValues(l1.next if l1 else None, l2.next if l2 else None, num, ratio * 10)
            else:
                return num

        sum_num = str(addListNodeValues(l1, l2, 0, 1))

        def numbersToListNode(num):
            if len(num) == 1:
                return ListNode(int(num[0]), None)
            return ListNode(int(num[-1]), numbersToListNode(num[0:-1]))
        return numbersToListNode(sum_num)

以下のとおりに動く ①各LinkedListの最初のノードの数値 * 今の桁数をnumに足していく ②LinkedListのどっちかがあれば、桁数を増やす&次のノードを指定して継続 ③継続できなくなったら、それまでの合計値を返して計算終了 ④合計値を一旦文字列に変換してからLinkedListを作り直す

ただ、ChatGPTにレビューしてもらったところ、LinkedList→Int→Str→LinkedListの変換コストがかかるので効率が悪いとの指摘があったため、以下のような形で修正した。

解答②

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def mergeListNode(l1, l2, carry):
            if not l1 and not l2 and not carry:
                return None
            num = carry
            if l1:
                num += l1.val
            if l2:
                num += l2.val
            carry = num // 10
            val = num % 10
            if l1 or l2:
                return ListNode(val, mergeListNode(l1.next if l1 else None, l2.next if l2 else None, carry))
            else:
                return ListNode(num, None)

        return mergeListNode(l1, l2, 0)

以下の通りに動く ①各LinkedListの最初のノードの数値を足す ②足した結果から、繰り上がり(carry)と、下一桁(val)を求める ③各LinkedListのどっちかがあれば、繰り上がりの数値を持ち越す&次のノードを指定して継続しつつ、下一桁を使って新しいLinkedListのノードを作る ④継続できなくなったら、新しく作ったLinkedListを返す

思ったこと

LinkedListはほぼ触ったことがなく、最初は扱いに苦戦した。 あと、まだ遠回りな発想しか出てこない感じがあるので、慣れておきたい。