给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
具体详情可以点进链接 题目这里就不做多余的解释了
题目分析
注意看提示
提示:
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
说明没有空链表 同时 肯定会越界
ok 我们就不能采用普通的办法了
代码
ok 我们看代码:
先看一个比较容易理解的
先取出数据,后计算结果,在组合答案并返回
int a[101];
int b[101];// 初始化 数组
int End[102];// 最后的结果数组
int i;
for(i=0;i<101;i++)
{
a[i]=b[i]=End[i]=0;// 初始化
}
// 我们先算出结果 然后将其写入结构体 然后返回
i=0;
ListNode * l=l1;
while (l) {
a[i++]=l->val;
l=l->next;// 取出l1
}
l=l2;
int aLength=i;
i=0;
while (l) {
b[i++]=l->val;
l=l->next;// 取出l2
}
int bLength=i;
int Cout=0;// 是否进位
int endLength=aLength >bLength? aLength :bLength;// 取最长的长度
for (i=0; i<endLength; i++) {
//进位位
Cout=a[i]+b[i]+Cout;
End[i]=Cout%10;;
Cout/=10;
}
if (Cout>0) {// 最高位是否发生进位 进位长度加一
End[endLength]=Cout;
endLength++;
}
ListNode *List =new ListNode;
l=List;
l->val=End[0];// 先把第一位放进去
for(i=1;i<endLength;i++)
{
l->next=new ListNode;
l=l->next;
l->val=End[i];
l->next=NULL;
}
// cout << endl;// 输出验证
l=List;
// while (l) {
//
cout << l->val << "->";
//
l=l->next;
// }
return List;
看一下结果:
执行用时: 52 ms
内存消耗: 69.4 MB
不过这个代码的效率可能会比较低 : 超越了20%的提交记录,不过这个更容易看懂
看一个更简便的方式 ,
int Cout =0;
ListNode * Lis = new ListNode;
ListNode * l=Lis;
while(l1 && l2){
Lis->next=new ListNode;
Lis=Lis->next;
Cout=Cout+l1->val+l2->val;
l1=l1->next;
l2=l2->next;
Lis->val=Cout%10;
Cout/=10;
}
while (l1) {
Cout+=l1->val;
l1=l1->next;
Lis->next=new ListNode;
Lis=Lis->next;
Lis->val=Cout%10;
Cout/=10;
}
while (l2) {
Cout+=l2->val;
l2=l2->next;
Lis->next=new ListNode;
Lis=Lis->next;
Lis->val=Cout%10;
Cout/=10;
}
if(Cout>0){
Lis->next =new ListNode;
Lis = Lis->next;
Lis->val=Cout;
Lis->next=NULL;
}
return l->next;
这个就不加注释了 ,和上面原理差不多。
这个的结果:
执行结果:
执行结果:
通过
执行用时:32 ms, 在所有 C++ 提交中击败了86.94%的用户内存消耗:69.6 MB, 在所有 C++ 提交中击败了14.75%的用户
时间上就会快很多 不过也跟处理机有关,就上面这个代码,我交了好多次,还出现过52ms的情况
总结
这里主要考察大数加法 原理根小时候学的加法一模一样 ,相信看过上面代码就理解个差不多了,就不多解释了。