两个单链表生成相加链表
一、题目
给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。
1
2
| 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912
|
leetcode：https://leetcode.cn/problems/sum-lists-lcci/
二、思路
现在链表已经是反向存放的，那我们只需要依次、同时遍历这两个链表，将两个节点上的数进行相加即可。一定要注意进位，我们可以使用一个变量来保存这个进位。在下一次计算的时候加上这个进位。两个链表遍历完之后也不要忘记这个进位
三、code
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
| struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* res = nullptr, *tmp_node = nullptr;
int ca = 0;
for (; l1 != nullptr || l2 != nullptr;) {
int cur_data = 0;
if (l1 != nullptr) {
cur_data += l1->val;
l1 = l1->next;
}
if (l2 != nullptr) {
cur_data += l2->val;
l2 = l2->next;
}
cur_data += ca;
if (cur_data >= 10) {
cur_data -= 10;
ca = 1;
} else {
ca = 0;
}
ListNode* tmp = new ListNode(cur_data);
if (res == nullptr) {
res = tmp;
tmp_node = tmp;
} else {
tmp_node->next = tmp;
tmp_node = tmp_node->next;
}
}
if (ca != 0) {
ListNode* tmp = new ListNode(ca);
tmp_node->next = tmp;
}
return res;
}
};
|
四、扩展
假设这些数位是正向存放的，又该如何解决呢?
1
2
| 输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912
|
其实这种存储方式也比较好解决，可以使用栈来获取倒置的链表。或者进行反转链表。
如果碰到倒置类型的东西，一定要想到栈这种数据结构。