445. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 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]
提示：
- 链表的长度范围为
[1, 100]
0 <= node.val <= 9
- 输入数据保证链表代表的数字无前导 0
进阶：如果输入链表不能翻转该如何解决？
法1 翻转 相加 再翻转
思路
因为高位在前，所以先翻转，然后相加，最后再翻转回去
题解·
# 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: l1 = self.reverse(l1) l2 = self.reverse(l2) res = self.add(l1, l2) return self.reverse(res) def add(self, l1, l2): """不创建新节点的加法 """ if l1 is None or l2 is None: return l1 if l2 is None else l2 res = l1 carry = 0 prev = None while l1 and l2: temp = carry + l1.val + l2.val l1.val = temp % 10 carry = temp // 10 prev = l1 l1 = l1.next l2 = l2.next if l2: prev.next = l2 l1 = l2 while l1: temp = carry + l1.val l1.val = temp % 10 carry = temp // 10 prev = l1 l1 = l1.next if carry: prev.next = ListNode(carry) return res def reverse(self, node): if node is None or node.next is None: return node prev, cur = None, node while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev