You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

你有两个非空的链表，表示两个非负整数。数字以反向顺序存储，每个节点包含一个数字。两个数字求和并将数字作为一个新的链表返回。

你可以假设这两个数字不包含任何前导零，除了数字0本身。

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

思路

这个题目很容易会想到先把链表转化为整数，求和之后再转回链表。但是这样很容易导致数字溢出 int 整型最大范围。所以这个方法不可行。

从示例中，不难发现整个计算的过程可以通过递归来表示。

例如：[2，4，3，1]和 [5，6，4]

1
2
[2，4，3，1]
[5，6，4，(0)]

两个链表的长度虽然不一定一致，但是可以通过将短的补 0 解决。首先随机选取纵向一列，如4,6（第二列）。作为链表的第二个节点，它的值 val 受第一列节点[2,5]之和的影响，可能进位；同时又要考虑其本身可能导致的进位而需要对10取余。

这个过程代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode getNextIgnoreNull(ListNode node) {
    return node == null ? null : node.next;
}
// 计算下一个节点
void nextNode(ListNode prev, ListNode l1, ListNode l2, int carry) {
	// 前一个节点为空，或者两个节点同时为空或者没有进位时，表示两个链表都已经循环完毕。
    if (prev == null || (l1 == null && l2 == null && carry == 0)) {
        return;
    }
    // 第一个链表对应位置的值，节点为空用 0 代替
    int num1 = l1 == null ? 0 : l1.val;
    // 第二个链表对应位置的值，节点为空用 0 代替
    int num2 = l2 == null ? 0 : l2.val;
    int sum = num1 + num2 + carry;
    prev.next = new ListNode(sum % 10);
    nextNode(prev.next, getNextIgnoreNull(l1), getNextIgnoreNull(l2), sum / 10);
}

上面列出了每一个节点的计算方式，题目中给出的两个初始链表l1和l2。如下，构造一个临时节点作为虚拟的首节点，递归执行。

1
2
3
4
5
6
7
// 程序入口 main()
ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // 临时节点
    ListNode temp = new ListNode(0);
    nextNode(temp, l1, l2, 0);
    return temp.next;
}

当然，递归虽然方便理解，但是其在执行过程中，会构建很多方法，内存占用较大。所以可以改写成如下：（使用while循环代替）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode prev = new ListNode(0);
    ListNode head = prev;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = ((l2 == null) ? 0 : l2.val) + ((l1 == null) ? 0 : l1.val) + carry;
        carry = sum / 10;
        prev.next = new ListNode(sum % 10);
        prev = prev.next;

        l1 = (l1 == null) ? l1 : l1.next;
        l2 = (l2 == null) ? l2 : l2.next;
    }
    return head.next;
}

题目来源：2. Add Two Numbers