两数相加
家人们！！！上链接！！！ 两数相加
题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
我们来看看题目，，，，往往困难的题只需要 简单的叙述。好像只用找到两个数，整合成一个链表就可以。这里的相加是一个一个节点的相加，可以想到加法器的思路。来看样例：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
从右边开始逐渐相加即可。样例非常清楚！！！
1 思路一 （暴毙版）
- 首先 我最快想到思路是 分别根据两个链表求出对应数
- 然后加一起 ，得到和
- 再把和拆分储存到链表里
为此我们需要手撕一下链表头插。（如果使用C++的STL库会很方便，这里C语言也更锻炼我们的思路）！！！
typedef struct ListNode SLTNode; SLTNode* buynode(int n) { //开辟空间 SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode)); node->next = NULL; node->val = n; return node; } void pushback(SLTNode** ret, int n) { //创建节点 SLTNode* node = buynode(n); //如果头为空 node成为头 if (*ret == NULL) { *ret = node; return; } //找尾 SLTNode* cur = *ret; while(cur->next) { cur = cur->next; } //插入 cur->next = node; return; } SLTNode* addTwoNumbers(SLTNode* l1, SLTNode* l2) { //选择long long 来储存较大数 long long num1 = 0, num2 = 0; long long a = 1; //计算数一 while (l1 != NULL) { num1 += (l1->val) * a; l1 = l1->next; a *= 10; } a = 1; //计算数二 while (l2 != NULL) { num2 += (l2->val) * a; l2 = l2->next; a *= 10; } //求和 long long sum = num1 + num2; //构建链表 SLTNode* ret = NULL; if(sum == 0) { pushback(&ret,0); return ret; } while (sum != 0) { long long n = sum % 10; pushback(&ret, n); sum = sum / 10; } //返回链表 return ret; }
一顿操作猛如虎，一看提交原地杵········
Line 39: Char 11: runtime error: signed integer overflow: 1000000000000000000 * 10 cannot be represented in type 'long long int' [solution.c]
虽然我已经使用最大的数据类型 long long ,但是最后的测试数据太大，还有3 个样例无法通过。这下子要从头开始了。
（这就得夸夸力扣了，丰富的测试用例，不会随便让你过）
该算法的弊端就显现出来了，我们是在数据类型的基础上操作，而不是在本质上进行相加！！！
2 思路二 （本质出发）
思路一的简单加和不能完成目的，那我们只好深入到加法的本质中去：
按位计算，满10进一 ,逐个逐个计算
这样就算把天文数字填进来，只要内存够，咱都能解决!!!
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode Listnode; struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { //创建头结点 Listnode* head = (Listnode*)malloc(sizeof(Listnode)); //创建尾指针 Listnode* cur = head; //进位数 int t = 0; //l1 l2 t 全为空才停止 while(l1||l2||t){ //l1 为真则把值赋值在t上 if(l1) { t += l1->val; l1 = l1->next; } //l2 为真则把值赋值在t上 if(l2) { t += l2->val; l2 = l2->next; } //创建节点 cur->next = ( Listnode *)malloc(sizeof(Listnode)); cur->next->val = t % 10; cur->next->next = NULL; //向后移动 cur = cur->next; t /= 10; } return head->next; }
一气呵成，呼~~~~
我们舍去手撕链表头插的痛苦。直接改为“满足条件”就开辟新空间。因此为了方便这里使用带头链表。
提交！ 过过过过啦！！！！！！
来看看性能怎么样，打败了80%的用户，10ms.
来分析一下咱们算法的时间复杂度 ，遍历链表，最坏情况也是遍历了一条很长的链表。那咱时间复杂度就是O(n)。啊？还有比 O(n) 更快的算法？？？答案是肯定没有，运行速度的具体原因和配置环境有关。咱们的代码冲一冲也可以0ms。
这道题考察了咱们对循环的认识，通过循环实现加法器。进而完成题目！
