2.两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
思路
基本思想
主要是模拟相加的过程，需要考虑进位，基本上使用了暴力法，从头开始遍历两个链表，两个节点相加，余10是当前位的结果，除10是下一位的进位，知道这些之后，就是代码的模拟，需要注意当前位相加得到结果之前，需要现将上一位的进位取出来，否则会出现覆盖的情况，在代码中为：
1
2
3
4
| num=l1->val+l2->val;
//相加之后是否需要进位
res[index]=(num+res[index])%10;
res[index+1]=(num+res[index])/10;
|
这种代码就会将当前位的进位抹去，导致第四行的结果出错
执行流程
- 从头开始遍历两个链表
- 将两个链表的节点值相加，再加上进位，余10得到当前位的结果，除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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public:
//从低位开始加，然后出现进位就向高位进位
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
vector<int> res(101,0);
int index=0,num=0;
while(l1!=nullptr&&l2!=nullptr){
//需要先考虑进位，否则真正的进位会被覆盖
num=l1->val+l2->val+res[index];
//相加之后是否需要进位
res[index]=(num)%10;
res[index+1]=(int)(num)/10;
index++;
l1=l1->next;
l2=l2->next;
}
//到了这里由于节点的范围不超过9，所以直接拿出来即可
while(l1!=nullptr){
num=l1->val+res[index];
res[index]=(num)%10;
res[index+1]=(num)/10;
index++;
l1=l1->next;
}
while(l2!=nullptr){
num=l2->val+res[index];
res[index]=(num)%10;
res[index+1]=(num)/10;
index++;
l2=l2->next;
}
index=res[index]==0?index:index+1;
res.resize(index);
//到这里加法统计结束,需要形成链表
ListNode* dummyHead=new ListNode(0);
ListNode* node=dummyHead;
for(auto val:res){
ListNode* temp=new ListNode(val);
node->next=temp;
node=node->next;
}
node->next=nullptr;
return dummyHead->next;
}
};
|
总结
就是简单的代码模拟，主要是要考虑进位