# LeetCode Medium 2. Add Two Numbers

tags: leetcode

問題

• Explore
• Problems

アイデア

｢空でない2つの非負整数を表現する連結リストが与えられる．それらの桁は反対順に入れられており，それぞれ単一の桁を持つ．2つの数を足した値を連結リストで返せ｣という問題です．

問題なのは桁上がりくらいですかね．実装するだけです．

解法

リストの要素を最初から見て，最初の要素から足していけば良さそうです．

計算量

連結リストのノード数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

Python

# 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: ListNode, l2: ListNode) -> ListNode:
        p, q = l1, l2
        cur= res = ListNode(0)
        carry = 0
        while p or q:
            l1_val = p.val if p else 0
            l2_val = q.val if q else 0
            cur_num = carry + l1_val + l2_val
            carry = cur_num // 10
            cur.next = ListNode(cur_num % 10)
            cur = cur.next
            if p:
                p = p.next
            if q:
                q = q.next
        if carry:
            cur.next = ListNode(carry)
        return res.next