政府 网站建设互联网营销师培训教程

两数相加

我们来看看题目，，，，
往往困难的题只需要 简单的叙述。

好像只用找到两个数，整合成一个链表就可以。应该

1 思路一 （暴毙版）

1. 首先 我最快想到思路是 分别根据两个链表求出对应数
2. 然后加一起 ，得到和
3. 再把和拆分储存到链表里
   为此我们需要手撕一下链表头插。

 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;
}

一顿操作猛如虎，一看提交原地杵········

虽然我已经使用最大的数据类型 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。
这道题考察了咱们对循环的认识，通过循环把加法本质实现。进而完成题目！

谢谢阅读Thanks♪(･ω･)ﾉ

下一篇文章见！！！！！！