LeetCode解説　一日一問　2.Add Two Numbers

LeetCodeって？
問題
回答
1. コード
結果

LeetCodeって？

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。

2022年12月現在2,000問を超える問題が登録されています。

各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。

正誤判定は自動で行われます。

使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。

私はPython3で解いています。

問題

Add Two Numbers - LeetCode

Can you solve this real interview question? Add Two Numbers - You are given two non-empty linked lists representing two non-negative integers. The digits are st...

タイトル：2. Add Two Numbers

難易度：medium

内容：

2 つの負でない整数を表す連結リストl1、l2が与えられる。数字は逆順で格納されている。l1、l2を加算しその合計を同じフォーマットの合計を連結リストで返す。

例：

連結リストに格納された数値が2→4→3だとすると逆順なので324を表します。

l1、l2がそれぞれ2→4→3、5→6→4の場合、324+564=807なので返り値は7→0→8となります。

足し算のひっ算をプログラムするような感じです。

回答

まず入出力する連結リストですが、このように定義されています。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

valにリストの先頭の値、nextに次の値が入っています。

まずは返り値用のListNodeを宣言します。

# 返り値初期化
dummyHead = ListNode(0)
curr = dummyHead

l1、l2を別の変数に代入しておきます。

また桁上がり用の変数も初期化します。

cur_l1 = l1
cur_l2 = l2
        
# 桁上がり
carry = 0

1の位の計算：cur_l1.val( = 2) + cur_l2.val( = 6) = 8　→　1の位：8、桁上がり：0

1の位の計算が終わったらcur_l1 = cur_l1 .nextとして先頭ノードを10の位にします。

10の位の計算：cur_l1.val( = 4) + cur_l2.val( = 6) = 10 > 9　→　1の位：0、桁上がり：1

同様にcur_l1 = cur_l1 .nextとして先頭ノードを100の位にします。また桁上がりを100の位に渡します。

以上の計算をcur_l1とcur_l2が空になるまで、かつ桁上がりがない状態まで継続します。l1とl2の桁が違う場合があるので、どちらも空になるまで計算を継続する必要があります。また、l1、l2が空になっても桁上がりがある場合（例えば500+500=1000）があるので、計算収量は桁上がりもなくなっている状態にする必要があります。

コードは以下です。

while cur_l1 is not None or cur_l2 is not None or carry == 1:
            
            # 空なら0、空でなければ今のノードを保持し次のノードをセット
            if cur_l1 is None:
                l1_n = 0
            else:
                l1_n = cur_l1.val
                cur_l1 = cur_l1.next
            if cur_l2 is None:
                l2_n = 0
            else:
                l2_n = cur_l2.val
                cur_l2 = cur_l2.next

            # 足し算
            n = l1_n + l2_n + carry
            
            # 足した値が9より多きければ桁上がり
            if n > 9:
                n = n % 10
                carry = 1
            else:
                carry = 0

            # 足し算の結果をセット
            newNode = ListNode(n)
            curr.next = newNode
            curr = newNode

コード

#全文
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 返り値用変数初期化
        dummyHead = ListNode(0)
        curr = dummyHead
        
        # 現在のl1,l2
        cur_l1 = l1
        cur_l2 = l2
        
        # 桁上がり
        carry = 0
        
        # cur_l1,cur_l2のいずれかがまだ空でない、またはけえた上がりがある場合は計算継続
        while cur_l1 is not None or cur_l2 is not None or carry == 1:
            
            # 空なら0、空でなければ今のノードを保持し次のノードをセット
            if cur_l1 is None:
                l1_n = 0
            else:
                l1_n = cur_l1.val
                cur_l1 = cur_l1.next
            if cur_l2 is None:
                l2_n = 0
            else:
                l2_n = cur_l2.val
                cur_l2 = cur_l2.next

            # 足し算
            n = l1_n + l2_n + carry
            
            # 足した値が9より多きければ桁上がり
            if n > 9:
                n = n % 10
                carry = 1
            else:
                carry = 0

            # 足し算の結果をセット
            newNode = ListNode(n)
            curr.next = newNode
            curr = newNode

        return (dummyHead.next)

コードはgithubにも保管しています。