问题描述
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
问题分析与思路
一开始题目的意思看了好久，没能理解，又多看了几遍，发现其实题目的意思很简单，就拿问题描述中的测试用例来说，其实是两个数324+465=807，只不过在存储的时候是反过来存储的。
这样一来，其实题目就变得很简单了，就是两个链表在进行相同位的相加，变成了链表的操作，同时需要考虑进位的问题，考虑多种情况，比如说两个数字长度不一样长的情况，进位情况等等。
在我自己写代码提交的时候发现有个测试用例没有过，[5]+[5]=[0,1]，我的代码的出来的结果是[0]，原因是忘记了最前面的进位，如果最后仍有进位，则需要多一位。
问题求解
C++的解决方案：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/*
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* sum = (ListNode*)malloc(sizeof(ListNode));
ListNode* point = sum;
int advance = 0;
while (l1 != NULL) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (l2 != NULL) {
newNode->val = (l1->val + l2->val + advance) % 10;
advance = (l1->val + l2->val + advance) / 10;
l1 = l1->next;
l2 = l2->next;
}
else {
newNode->val = (l1->val + advance) % 10;
advance = (l1->val + advance) / 10;
l1 = l1->next;
}
point->next = newNode;
point = newNode;
}
if (l2 != NULL) {
while (l2 != NULL) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = (l2->val + advance) % 10;
advance = (l2->val + advance) / 10;
point->next = newNode;
point = newNode;
l2 = l2->next;
}
}
if (advance != 0) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = advance;
point->next = newNode;
point = newNode;
}
point->next = NULL;
return sum->next;
}
};
其实这里都是链表的一些操作，但是需要考虑到l1和l2的长度问题，while语句里面考虑到的是l1的长度>=l2的长度的情况，后面则是考虑到l1的长度小于l2的长度的情况。用int型的advance来保存进位的值，每次都计算是否有进位，直接%10得到保存在链表的值，/10得到进位的值，最后不要忘记如果advance!=0的时候需要加上进位。
附上网上别人写的解决方案，代码比我的简洁多了，可以学习。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23//时间复杂度 O(m+n)，空间复杂度 O(1)
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode dummy(-1); // 头节点
int carry = 0;
ListNode *prev = &dummy;
for (ListNode *pa = l1, *pb = l2;
pa != nullptr || pb != nullptr;
pa = pa == nullptr ? nullptr : pa->next,
pb = pb == nullptr ? nullptr : pb->next,
prev = prev->next) {
const int ai = pa == nullptr ? 0 : pa->val;
const int bi = pb == nullptr ? 0 : pb->val;
const int value = (ai + bi + carry) % 10;
carry = (ai + bi + carry) / 10;
prev->next = new ListNode(value); // 尾插法
}
if (carry > 0)
prev->next = new ListNode(carry);
return dummy.next;
}
};
相关知识点总结
单链表
这里总结了单链表的一些常用的的操作。（先在这里列着，有时间再来补充全，原谅我这个时候有点偷懒了，嘿嘿~）