NeetCode 150 [Linked List] medium : Add Two Numbers

NeetCodeのSolutionを書いていく

Add Two Numbers

問題

2つの空ではないリンクリストl1,l2が与えられます。それぞれ負ではない整数です。
数字は逆順に格納されます。つまり、123は3,2,1として存在します。

それぞれのノードは一つの数字を含みます。
0以外に0から始まる数字はありません。
2つのリンクリストを足し合わせたリンクリストを返しなさい。

制約

• l1, l2 の長さは1以上100以下
• nodeの値は0以上9以下

計算量：O(m+n) mはl1の長さ、nはl2の長さ
メモリ：O(1)

例

Input: l1 = [1,2,3], l2 = [4,5,6]
Output: [5,7,9]
Explanation: 321 + 654 = 975.

Input: l1 = [9], l2 = [9]
Output: [8,1]

メモ

問題を違う言葉で表現すると。

• 数字が逆順(リトルエンディアンな感じ)にリンクリストに格納されている
• 数字は2つ与えられる
• 2つの数字を復元する
• 2つの数字を足す
• 足した結果を逆順のリンクリストに戻して返す

これをO(m+n)回でやる。
単に上に書いた手順を実施するのではだめなんだろうか。

ヒントを見ると、桁が小さい方から並んでいるので、順番に足し算をしていけばいいだけらしい。
ポイントは繰り上がりの数だけ。
確かにこれならシンプル。

from typing import Optional


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


class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        node1, node2 = l1, l2
        retval: ListNode = ListNode(0)  # dummy
        node = retval
        carry = 0

        while node1 or node2:
            if node1 and node2:
                add = node1.val + node2.val + carry
            elif node1:
                add = node1.val + carry
            elif node2:
                add = node2.val + carry

            digit = add % 10
            carry = add // 10
            node1 = None if not node1 else node1.next
            node2 = None if not node2 else node2.next

            if node:
                node.next = ListNode(digit)
                node = node.next
            else:
                node = ListNode(digit)

        if carry:
            node.next = ListNode(carry)

        return retval.next