问题描述：

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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：进位标识符

初始化

第二步

1. 取出L1, L2的值（当前指向第一个节点，值分别是 2 和 5 ），并将L1, L2 指向下一个节点（移动后指向第二个节点，值分别是 4 和 6 ）
2. 第一次相加，2 + 5 + 0 = 7（进位标识默认为 0 ）。相加后也无进位标识(carry = 0)。

3. 创建节点7，将last指针指向7。

   
   2 + 5

第三步

1. 取出L1, L2的值（当前指向第二个节点，值分别是 4 和 6 ），并将L1, L2 指向下一个节点（移动后指向第三个节点，值分别是 3 和 4 ）
2. 上一步操作无进位(carry = 0)，4 + 6 + 0 = 10。相加后有进位标识(carry = 1)。

3. 创建节点 0，将last指针指向 0。

   
   4 + 6

第四步

1. 取出L1, L2的值（当前指向第三个节点，值分别是 3 和 4 ），并将L1, L2 指向下一个节点（移动后指向空）
2. 上一步操作有进位（carry = 1），3 + 4 + 1 = 8。相加后无进位标识（carry = 0）.

3. 创建节点8，将last指针指向8.

   
   3 + 4

第五步

1. 由于L1, L2指向空，结束循环。
2. 还需判断最后一位相加是否有进位，有则创建节点 1。

3. 返回 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 表示传入链表的长度。
空间复杂度：