问题描述：
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。题目难度：中等
来源：力扣（LeetCode）
原题连接
示例
# 示例 1：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
示例 1 图片
# 示例 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]
题解
1. 思路
本题的关键是指针，想清楚如何通过指针的移动完成两数求和。
2. 图解
第一步
L1, L2为传入的两个链表，由于采用逆序存储。可以直接遍历链表求和。
dummyHead：虚拟头节点，返回最终结果时使用
last：尾节点
carry：进位标识符
初始化
第二步
- 取出L1, L2的值（当前指向第一个节点，值分别是 2 和 5 ），并将L1, L2 指向下一个节点（移动后指向第二个节点，值分别是 4 和 6 ）
- 第一次相加，2 + 5 + 0 = 7（进位标识默认为 0 ）。相加后也无进位标识(carry = 0)。
创建节点7，将last指针指向7。
2 + 5
第三步
- 取出L1, L2的值（当前指向第二个节点，值分别是 4 和 6 ），并将L1, L2 指向下一个节点（移动后指向第三个节点，值分别是 3 和 4 ）
- 上一步操作无进位(carry = 0)，4 + 6 + 0 = 10。相加后有进位标识(carry = 1)。
创建节点 0，将last指针指向 0。
4 + 6
第四步
- 取出L1, L2的值（当前指向第三个节点，值分别是 3 和 4 ），并将L1, L2 指向下一个节点（移动后指向空）
- 上一步操作有进位（carry = 1），3 + 4 + 1 = 8。相加后无进位标识（carry = 0）.
创建节点8，将last指针指向8.
3 + 4
第五步
- 由于L1, L2指向空，结束循环。
- 还需判断最后一位相加是否有进位，有则创建节点 1。
返回 dummyHead.next。
判断最后是否有进位并返回结果
3. 源码
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
// 虚拟链表头节点
ListNode dummyHead = new ListNode(-1);
// 链表尾节点
ListNode last = dummyHead;
// 进位标识
int carry = 0;
while (l1 != null || l2 != null) {
// 取出 L1的值，并使L1指向下一个节点
int v1 = 0;
if (l1 != null) {
v1 = l1.val;
l1 = l1.next;
}
// 取出 L2的值，并使L2指向下一个节点
int v2 = 0;
if (l2 != null) {
v2 = l2.val;
l2 = l2.next;
}
// 根据L1, L2, carry（进位）的值求和
int sum = v1 + v2 + carry ;
// 设置进位
carry = sum / 10;
// 创建新节点
last.next = new ListNode(sum % 10);
// 将last指向新创建的节点
last = last.next;
}
// 检查最后的进位
if (carry > 0) {
last.next = new ListNode(1);
}
return dummyHead.next;
}
4. 复杂度分析
时间复杂度：
，m, n 表示传入链表的长度。
空间复杂度：
