很常规的一道题..
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
其实就是相当于常规的大数加减：链表版本（老OIer应该都写过无数遍了
解法一：链表逆序
将两个链表先重新构造成其逆序链表，再逐位进行运算即可
构造代码如下：
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
if(!l1)
return l2;
if(!l2)
return l1;
struct ListNode * temp = NULL, *temp2;
while(l1)
{
temp2 = l1->next;
l1->next = temp;
temp = l1;
l1 = temp2;
}
l1 = temp;
temp = NULL;
while(l2)
{
temp2 = l2->next;
l2->next = temp;
temp = l2;
l2 = temp2;
}
l2 = temp;
int flag = 0;
struct ListNode * retn = (struct ListNode*)malloc(sizeof(struct ListNode));
retn->next = NULL;
while(l1&&l2)
{
retn->val = (l1->val + l2->val + flag) % 10;
flag = (l1->val + l2->val + flag) / 10;
temp = retn;
retn = (struct ListNode*)malloc(sizeof(struct ListNode));
retn->next = temp;
l1 = l1->next;
l2 = l2->next;
}
while(l1)
{
retn->val = (l1->val + flag) % 10;
flag = (l1->val + flag) / 10;
temp = retn;
retn = (struct ListNode*)malloc(sizeof(struct ListNode));
retn->next = temp;
l1 = l1->next;
}
while(l2)
{
retn->val = (l2->val + flag) % 10;
flag = (l2->val + flag) / 10;
temp = retn;
retn = (struct ListNode*)malloc(sizeof(struct ListNode));
retn->next = temp;
l2 = l2->next;
}
if(flag)
{
retn->val = flag;
return retn;
}
return retn->next;
}
|
解法二：栈
进阶解法要求我们不对链表进行重构
当然，既然是逆序运算，我们很容易就能够联想到另外一种受限线性表——栈
我们可以先将两个链表的结点值分别压入两个数组模拟的栈中，这样就变成我们最常见也最喜欢的常规的大数加减了
构造代码如下：
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
56
57
58
59
60
61
62
63
|
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
if(!l1)
return l2;
if(!l2)
return l1;
int * n1 = (int*) malloc(sizeof(int) * 99), *n2 = (int*) malloc(sizeof(int) * 99), *temp, temp2;
int len1 = 0, len2 = 0;
while(l1)
{
n1[len1++] = l1->val;
l1 = l1->next;
}
while(l2)
{
n2[len2++] = l2->val;
l2 = l2->next;
}
if(len1<len2)
{
temp = n1;
n1 = n2;
n2 = temp;
temp2 = len1;
len1 = len2;
len2 = temp2;
}
struct ListNode * retn = (struct ListNode*)malloc(sizeof(struct ListNode)), *tmp;
retn->next = NULL;
int flag = 0;
for(len1--,len2--;len2>=0;len1--,len2--)
{
retn->val = (n1[len1] + n2[len2] + flag) % 10;
flag = (n1[len1] + n2[len2] + flag) / 10;
tmp = retn;
retn = (struct ListNode*)malloc(sizeof(struct ListNode));
retn->next = tmp;
}
while(len1!=-1)
{
retn->val = (n1[len1] + flag) % 10;
flag = (n1[len1] + flag) / 10;
tmp = retn;
retn = (struct ListNode*)malloc(sizeof(struct ListNode));
retn->next = tmp;
len1--;
}
if(flag)
{
retn->val = flag;
return retn;
}
return retn->next;
}
|
当然，因为需要额外的栈空间，所以空间复杂度上不是很理想（分明是退阶解法
