力扣第二题，两数相加
最近在尝试做一下leetcode，零基础起步
审题
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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
- 题目数据保证列表表示的数字不含前导零
原始题目：
1
2
3
4
5
6
7
8
9
10
|
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
}
|
这里说一下，leetcode中的题目是没有main函数的，完成给出函数的补全即可。
思路
给了两个链表，本质上是加减，正序反序其实无所谓，那么如何加？
- 直接一一对应加，需要考虑进位
- 先把题目给出两个链表的数值算出来，然后分别取个十百位再创建链表
第二种比较麻烦，有很多取余取整，故这里采用第一种方法。
一上来先申请一块内存空间来做指针，一会return出去，然后标准初始化
1
2
| struct ListNode* p = (struct ListNode *)malloc(sizeof(struct ListNode));
p->next = NULL;
|
紧接着申请另外一个指针，来辅助操作（可以直接对辅助指针进行迭代操作，返回的时候只返回原始指针的next指针）
1
2
3
| struct ListNode* t = (struct ListNode *)malloc(sizeof(struct ListNode));
t->next = NULL;
t = p;
|
然后就是相加的部分了，首先是l1，l2不能为空，然后定义一个临时指针通过后插扩充链表，计算的过程涉及到了进位，所以用flag来表示是否产生进位，在没有产生进位的情况下，链表对应位置的值就是l1，l2相应位置的值之和，直接相加即可，如果产生了进位，就在l1，l2基础上加1。
是否产生进位，就看l1，l2 (+1)对应的值是否大于9，如果大于，取余赋值，并将flag设置为1，否则直接赋值，flag设置为0；
剩下就是常规的后插法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int flag = 0;
while(l1&&l2){
int temp = 0;
struct ListNode* s = (struct ListNode *)malloc(sizeof(struct ListNode));
s->next = NULL;
if(flag){
temp = l1->val + l2->val + 1;
}else temp = l1->val + l2->val;
flag = 0;
if(temp > 9){
s->val = temp%10;
flag = 1;
}else s->val = temp;
t->next = s;
t = t->next;
l1 = l1->next;
l2 = l2->next;
}
|
但是测试时发现有一种情况没有考虑，即两链表长度未必相同：
输入
l1 = [9,9,9,9,9,9,9]
l2 = [9,9,9,9]
运行结果
[8,9,9,9]
预期结果
[8,9,9,9,0,0,0,1]
这明显是在l1或l2任一为空时停止了循环，为此我们需要继续把剩余的补充上去。
可以使用while(l1)和while(l2)来把未空的链表继续完成
我们仍然需要考虑进位，从简单的考虑，如果没有进位那么直接把剩余的节点直接尾插即可。
如果进位了，那么就需要把节点的val加1，后续仍然需要考虑进位问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| while(l1){
struct ListNode* s = (struct ListNode *)malloc(sizeof(struct ListNode));
s->next = NULL;
if(flag){
if(l1->val+1 > 9){
s->val = (l1->val + 1)%10;
}else{
s->val = l1->val + 1;
flag = 0;
}
}else{
s->val = l1->val;
}
t->next = s;
t = t->next;
l1 = l1->next;
}
|
l2同理，将l1改为l2即可。
运行代码，结果是
[8,9,9,9,0,0,0]
发现缺少了一位，显然，缺少的是进位，为此我们添加上
1
2
3
4
5
6
7
| if(flag){
struct ListNode* s = (struct ListNode *)malloc(sizeof(struct ListNode));
s->next = NULL;
s->val = 1
t->next = s;
t = t->next;
}
|
在最后，返回p指针的next指针（尾插法从next开始是第一个节点）
运行结果：
[8,9,9,9,0,0,0,1]
至此结束
代码
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
|
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
int num1,num2,num3;
struct ListNode* p = (struct ListNode *)malloc(sizeof(struct ListNode));
p->next = NULL;
struct ListNode* t = (struct ListNode *)malloc(sizeof(struct ListNode));
t->next = NULL;
t = p;
int flag = 0;
while(l1&&l2){
int temp = 0;
struct ListNode* s = (struct ListNode *)malloc(sizeof(struct ListNode));
s->next = NULL;
if(flag){
temp = l1->val + l2->val + 1;
}else temp = l1->val + l2->val;
flag = 0;
if(temp > 9){
s->val = temp%10;
flag = 1;
}else s->val = temp;
t->next = s;
t = t->next;
l1 = l1->next;
l2 = l2->next;
}
while(l1){
struct ListNode* s = (struct ListNode *)malloc(sizeof(struct ListNode));
s->next = NULL;
if(flag){
if(l1->val+1 > 9){
s->val = (l1->val + 1)%10;
}else{
s->val = l1->val + 1;
flag = 0;
}
}else{
s->val = l1->val;
}
t->next = s;
t = t->next;
l1 = l1->next;
}
while(l2){
struct ListNode* s = (struct ListNode *)malloc(sizeof(struct ListNode));
s->next = NULL;
if(flag){
if(l2->val+1 > 9){
s->val = (l2->val + 1)%10;
}else{
s->val = l2->val + 1;
flag = 0;
}
}else{
s->val = l2->val;
}
t->next = s;
t = t->next;
l2 = l2->next;
}
if(flag){
struct ListNode* s = (struct ListNode *)malloc(sizeof(struct ListNode));
s->next = NULL;
s->val = 1;
t->next = s;
t=t->next;
}
return p->next;
}
|