【Leetcode算法题】2. 两数相加

By Long Luo

2. 两数相加题目如下所示:

  1. 两数相加

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

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

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

示例 1:
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

示例 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, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

方法一:模拟链表操作

思路与算法:

最开始我的思路是将2个数字都读出来,然后相加,再逆向写入回去,但是发现链表数字太长,这个方法不可行。

由于两个链表长度不一致,还需要考虑不同位数对齐的问题,但是由于输入的两个链表都是逆序存储数字的位数的,因此两个链表中同一位置的数字可以直接相加

那么只需要同时遍历两个链表,逐位计算它们的和,并与当前位置的进位值相加。具体而言,如果当前两个链表处相应位置的数字为n1, n2,进位值为carry\textit{carry},则它们的和为n1+n2+carryn1+n2+\textit{carry}

其中,答案链表处相应位置的数字为(n1+n2+carry) mod 10,而新的进位值为sum - 10。

需要注意的是:如果链表遍历结束后,有carry>0,还需要在答案链表的后面附加一个节点,节点的值为carry。

于是就有了那么的第一版代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pNode1 = l1;
ListNode pNode2 = l2;
ListNode dummyNode = new ListNode(-1);
ListNode pNode = dummyNode;
int carry = 0;
while (pNode1 != null && pNode2 != null) {
int sum = pNode1.val + pNode2.val + carry;
carry = 0;
if (sum >= 10) {
sum -= 10;
carry = 1;
}
ListNode node = new ListNode(sum);
pNode.next = node;
pNode = pNode.next;

pNode1 = pNode1.next;
pNode2 = pNode2.next;
}

while (pNode1 != null) {
int sum = pNode1.val + carry;
carry = 0;
if (sum >= 10) {
sum -= 10;
carry = 1;
}
ListNode node = new ListNode(sum);
pNode.next = node;
pNode = pNode.next;

pNode1 = pNode1.next;
}

while (pNode2 != null) {
int sum = pNode2.val + carry;
carry = 0;
if (sum >= 10) {
sum -= 10;
carry = 1;
}
ListNode node = new ListNode(sum);
pNode.next = node;
pNode = pNode.next;
pNode2 = pNode2.next;
}

if (carry > 0) {
ListNode node = new ListNode(carry);
pNode.next = node;
}

return dummyNode.next;
}

实际上,上述代码可以优化,去掉多余的变量。如果两个链表的长度不同,则可以认为长度短的链表的后面有若干个00,得到了下面的优化代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyNode = new ListNode(-1);
ListNode pNode = dummyNode;
int carry = 0;
while (l1 != null || l2 != null) {
int num1 = l1 != null ? l1.val : 0;
int num2 = l2 != null ? l2.val : 0;
int sum = num1 + num2 + carry;
carry = sum / 10;
pNode.next = new ListNode(sum % 10);
pNode = pNode.next;

if (l1 != null) {
l1 = l1.next;
}

if (l2 != null) {
l2 = l2.next;
}
}

if (carry > 0) {
pNode.next = new ListNode(carry);
}

return dummyNode.next;
}

复杂度分析:

  • 时间复杂度:O(max(m,n))O(\max(m,n)),其中mmnn分别为两个链表的长度。我们要遍历两个链表的全部位置,而处理每个位置只需要O(1)O(1)的时间。

  • 空间复杂度:O(1)O(1)