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
[2431]
[564,(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