445 两数相加 II：给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。进阶：如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
1
2
| 输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
|
反转链表再遍历
其实我们可以利用 LeetCode 刷题之 206 反转链表 和 LeetCode 刷题之 2 两数相加 完成该题。
首先，将链表 l1 和链表 l2 反转，然后调用两数相加的代码，最后再对返回的链表再次反转即可。
时间复杂度：O(max(m, n))，空间复杂度：O(1)，不考虑输出占用的空间；递归调用栈的空间复杂度：O(max(m, n))，如果采用迭代的方式反转链表，则为常数空间。
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
| struct ListNode* reverseList(struct ListNode* head){
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode* tail = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return tail;
}
struct ListNode* addTwoNumbers_i(struct ListNode* l1, struct ListNode* l2) {
struct ListNode dummy;
struct ListNode *cur = &dummy;
int curSum = 0, carry = 0;
while (l1 || l2 || carry > 0) {
struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
node->next = NULL;
curSum = carry;
if (l1) {
curSum += l1->val;
l1 = l1->next;
}
if (l2) {
curSum += l2->val;
l2 = l2->next;
}
carry = curSum > 9 ? 1 : 0;
curSum = curSum % 10;
node->val = curSum;
cur->next = node;
cur = cur->next;
}
return dummy.next;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
l1 = reverseList(l1);
l2 = reverseList(l2);
struct ListNode* head = addTwoNumbers_i(l1, l2);
return reverseList(head);
}
|
LIFO 堆栈
进阶：如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
记住：如果需要考虑链表反转，首先考虑栈（后进先出）。
因此，我们可以申请两个栈空间，依次遍历两个链表，将节点按遍历顺序放入各自的堆栈中。然后，依次同时从两个堆栈中各弹出一个节点，进行两数相加，将相加形成的新节点，放入第三个堆栈中，直到相加操作结束。最后，依次弹出第三个堆栈中的节点，并将它们链接在一起，即为答案。
堆栈的实现：我们可以使用 数据结构之堆栈（数组实现）或 数据结构之堆栈（链表实现）中实现的堆栈数据结构。但是，为了简便，这里使用了普通数组来模拟堆栈。
时间复杂度：O(max(m, n))，空间复杂度：O(max(m, n))，即堆栈占用的空间，不考虑输出占用的空间。
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
| struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode *stack1[101], *stack2[101], *stack3[101];
struct ListNode *node1 = l1;
struct ListNode *node2 = l2;
int pos1 = 0, pos2 = 0, pos3 = 0;
while (node1) {
stack1[pos1++] = node1;
node1 = node1->next;
}
while (node2) {
stack2[pos2++] = node2;
node2 = node2->next;
}
pos1--;
pos2--;
int curSum = 0, carry = 0;
while (pos1 >= 0 || pos2 >= 0 || carry > 0) {
struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
node->next = NULL;
curSum = carry;
if (pos1 >= 0) {
curSum += stack1[pos1]->val;
pos1--;
}
if (pos2 >= 0) {
curSum += stack2[pos2]->val;
pos2--;
}
carry = curSum > 9 ? 1 : 0;
curSum = curSum % 10;
node->val = curSum;
stack3[pos3++] = node;
}
struct ListNode *ans = stack3[--pos3];
while (pos3 > 0) {
stack3[pos3]->next = stack3[pos3 - 1];
pos3--;
}
stack3[pos3]->next = NULL;
return ans;
}
|
