两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

约定

• 链表节点定义为 ListNode { val, next }。
• 数字按位逆序存储：链表头是个位。
• 加法要正确处理进位。

输入

• l1：第一个数的链表头，长度 1 ~ 100
• l2：第二个数的链表头，长度 1 ~ 100
• 节点取值 0 ~ 9

输出

表示和的链表头（同样逆序）。

示例一

输入：

l1 = [2,4,3], l2 = [5,6,4]

输出：

[7,0,8]

解释：342 + 465 = 807。

示例二

输入：

l1 = [0], l2 = [0]

输出：

[0]

示例三

输入：

l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

输出：

[8,9,9,9,0,0,0,1]

复杂度要求

• 时间复杂度：O(max(m,n))
• 空间复杂度：O(1)（不计输出链表）