[Leetcode][2. 两数相加] 2种方法:模拟 和 递归

By Long Luo

Leetcode 2. 两数相加 题解。

方法一:模拟链表操作

思路与算法:

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

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

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

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

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

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

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)

方法二:递归

递归更精妙,但也更难懂!

首先,需要确定终止条件,显然当l1l1或者l2l2为空指针时,递归终止;
其次,l1l1l2l2不为空时,结果为两者之和加上进位然后mod10mod 10

递归需要考虑进位,所以需要新写一个辅助函数,进位作为参数传递,这点比较难以想到。

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
public static ListNode addTwoNumbers_rec(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
}

return addNode(l1, l2, 0);
}

public static ListNode addNode(ListNode l1, ListNode l2, int carry) {
if (l1 == null && l2 == null && carry == 0) {
return null;
}

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

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

ListNode addNode = new ListNode(carry % 10);
carry = carry / 10;
addNode.next = addNode(l1, l2, carry);
return addNode;
}

复杂度分析

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

  • 空间复杂度:O(max(m,n))O(\max(m,n))


All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗