leetcode两数相加python

题目描述：

给定两个非空链表，表示两个非负整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

例如：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> -> 8
原因：342 + 465 = 807

解题思路：

1. 遍历两个链表，将对应的节点相加，如果有进位则加到下一位相加中。
2. 如果两个链表长度不一样，则将短链表的后面补，以便于相加。
3. 最后如果还有进位，则需要再新建一个节点。

Python代码实现：

class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
cur = dummy
carry =
while l1 or l2:
x = l1.val if l1 else
y = l2.val if l2 else
s = x + y + carry
carry = s // 10
cur.next = ListNode(s % 10)
cur = cur.next
if l1: l1 = l1.next
if l2: l2 = l2.next
if carry > :
cur.next = ListNode(carry)
return dummy.next

时间复杂度：O(max(m,n))，其中m和n分别为两个链表的长度。

空间复杂度：O(max(m,n))，需要新建一个链表来存储结果。