[LeetCode-02]-Add Two Numbers-性能极好
每周完成一个ARTS：(Algorithm、Review、Tip、Share, ARTS)
- Algorithm: 每周至少做一个 leetcode 的算法题
- Review: 阅读并点评至少一篇英文技术文章
- Tip: 学习至少一个技术技巧
- Share: 分享一篇有观点和思考的技术文章
题目相关
【题目】原题链接
You are given two non-empty linked lists representing two non-negative integers. 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.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
nput: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
【难度】Medium
Solution
1. 错误的解法
由于是数字，所以想到了先遍历list，将list中存放的数据还原原始数据值，之后再进行加操作，并将结果存放到list中。
代码：
ListNode *addTwoNumbers_bak(ListNode *l1, ListNode *l2)
{
int firstRet = calNumVal(l1);
int secondRet = calNumVal(l2);
int sum = firstRet + secondRet;
printf("%lld + %lld = %lld\n", firstRet, secondRet, sum);
ListNode *head = new ListNode(sum % 10);
sum /= 10;
ListNode *end = head;
while (sum != 0)
{
ListNode *newNode = new ListNode(sum % 10);
newNode->next = NULL;
end->next = newNode;
end = end->next;
sum /= 10;
}
return head;
}
//还原为实际数据
int calNumVal(ListNode *l1)
{
int ret = 0;
int index = 0;
ListNode *p = l1;
while (p != NULL)
{
ret += p->val * pow(10, index++);
p = p->next;
}
return ret;
}
但是该代码遇到大一点的数字就不能进行了，所以改为long long后，再次遇到下面更大的测试用例，不能进行。以上代码是上一周实现的，遇到那么大的list，感觉到束手无策，提交代码的时候发现自己的算法不具备通用性，能够计算的数据比较少，未完待续。
一个超长的测试用例：
[2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9]
[5,6,4,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9,9,9,9]
2. 正确解法
面对上面那么大数据的测试用例，先计算再存放的方法不可行，所以需要重新思考该题目的方法。经过分析，发现，存放两个加数的 list 以及 存放结果的 list 的存放规律，第一个结点实际上就是数据值的个位，可以直接进行加，在加法的情况下，也最多进位 1。 所以直接采用逐位进行加，把计算的结果存放到最终的 list中。
下面的代码和经典的两个链表进行排序合并算法类似，在两个都非空的情况下，直接进行加，如果其中一个遍历结束，再遍历另一个链表，直到两个都遍历完成。
代码如下：
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
ListNode *p1 = l1;
ListNode *p2 = l2;
ListNode *head = new ListNode(0);
ListNode *p_ret = head;
int flag = false; //是否有进位
//都非空的情况下直接进行加
while (p1 != NULL && p2 != NULL)
{
int temp = p1->val + p2->val;
//判断上次是否有进位
if (flag)
{
temp += 1;
}
//是否有进位，下次使用
if (temp >= 10)
{
flag = true;
}
else
{
flag = false;
}
p_ret->val = temp % 10;
p1 = p1->next;
p2 = p2->next;
if (p1 != NULL && p2 != NULL)
{
ListNode *new_node = new ListNode(0);
new_node->next = NULL;
p_ret->next = new_node;
p_ret = new_node;
}
}//end while
//p2或p1遍历结束的情况下，直接进行存放值，不过这里需要考虑进位的情况
//如下两个while只会执行其中一个
while (p1 != NULL)
{
ListNode *new_node = new ListNode(0);
new_node->val = p1->val;
new_node->next = NULL;
if (flag)
{
//连续进位的情况
int temp = new_node->val + 1;
if (temp >= 10)
{
flag = true;
}
else
{
flag = false;
}
new_node->val = temp % 10;
}
p_ret->next = new_node;
p_ret = new_node;
p1 = p1->next;
}
while (p2 != NULL)
{
ListNode *new_node = new ListNode(0);
new_node->val = p2->val;
new_node->next = NULL;
if (flag)
{
//连续进位的情况
int temp = new_node->val + 1;
if (temp >= 10)
{
flag = true;
}
else
{
flag = false;
}
new_node->val = temp % 10;
}
p_ret->next = new_node;
p_ret = new_node;
p2 = p2->next;
}
//flag为真，说明前面的加法中有进位未处理完成
if (flag)
{
ListNode *new_node = new ListNode(0);
new_node->val = 1;
new_node->next = NULL;
p_ret->next = new_node;
flag = false;
}
return head;
}
3. 几个用例
一个超长的测试用例：
[2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9]
[5,6,4,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9,9,9,9]
有进位的用例：
[5]
[5]
连续进位的情况：
[1,1]
[9,9,9]
后记
题目中使用的是不带头结点的单链表，处理起来比较麻烦，总有一些用例跑失败，说明自己的代码没有考虑完全，Accept后发现居然有1563个测试用例，完全通过不容易????。
后来发现，该算法在 C++ 提交的代码中，性能以及空间上都是前1%，牛逼了，也对得起在高铁上调试、提交代码的那个少年。
Runtime: 28 ms, faster than 99.36% of C++ online submissions for Add Two Numbers.
Memory Usage: 10.3 MB, less than 99.45% of C++ online submissions for Add Two Numbers.