给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
输入：num1 = “11”, num2 = “123”
输出：“134”
示例 2：
输入：num1 = “456”, num2 = “77”
输出：“533”
示例 3：
输入：num1 = “0”, num2 = “0”
输出：“0”
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
i, j, carry = len(num1)-1, len(num2)-1, 0
res = ''
while i >= 0 or j >= 0:
n1 = int(num1[i]) if i >= 0 else 0
n2 = int(num2[j]) if j >= 0 else 0
n = n1 + n2 + carry
carry = n // 10
res = str(n%10) + res
i, j = i-1, j-1
return '1'+res if carry else res
复杂度分析：
- 时间复杂度
O
(
m
a
x
(
M
,
N
)
)
O(max(M,N))
O(max(M,N))：其中
M
，
N
M，N
M，N 为
2
2
2 数字长度，按位遍历一遍数字（以较长的数字为准）；
- 空间复杂度
O
(
1
)
O(1)
O(1)：指针与变量使用常数大小空间。
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n 1 , n 2 n1,n2 n1,n2，进位值为 carry \textit{carry} carry，则它们的和为 n 1 + n 2 + carry n1+n2+\textit{carry} n1+n2+carry；其中，答案链表处相应位置的数字为 ( n 1 + n 2 + carry ) m o d 10 (n1+n2+\textit{carry}) \bmod 10 (n1+n2+carry)mod10，而新的进位值为 ⌊ n 1 + n 2 + carry 10 ⌋ \lfloor\frac{n1+n2+\textit{carry}}{10}\rfloor ⌊10n1+n2+carry⌋。
如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。
此外，如果链表遍历结束后，有 carry > 0 \textit{carry} > 0 carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry \textit{carry} carry。
# 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]:
head = current = ListNode()
res, newval = 0, 0 # 进位值和余数
while res or l1 or l2:
if l1: l1, newval = l1.next, l1.val + newval
if l2: l2, newval = l2.next, l2.val + newval
res, newval = divmod(newval,10)
current.next = current = ListNode(newval)
newval = res
return head.next
复杂度分析
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
示例2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]
示例3：
输入：l1 = [0], l2 = [0]
输出：[0]
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
def list_reverse(l):
prev, curr = None, l
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prev
def two_numbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
head = current = ListNode()
res, newval = 0, 0 # 进位值和余数
while res or l1 or l2:
if l1: l1, newval = l1.next, l1.val + newval
if l2: l2, newval = l2.next, l2.val + newval
res, newval = divmod(newval,10)
# current.next = current = ListNode(newval)
current.next = current = ListNode(newval)
newval = res
return head.next
dummy = ListNode(-1)
l1, l2 = list_reverse(l1), list_reverse(l2)
return list_reverse(two_numbers(l1, l2))