网站建设的技术可行性,做推文加入视频的网站,下载深圳app,wordpress自定义简单注册文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 总结 前言
这道题使用链表来实现加法运算#xff0c;主要是涉及到数据对位以及加法进位的处理。 题目
假设链表中每一个节点的值都在 0 - 9 之间#xff0c;那么链表整体就可以代表一个整数。 给定两个这种链表#xff0… 文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 总结 前言
这道题使用链表来实现加法运算主要是涉及到数据对位以及加法进位的处理。 题目
假设链表中每一个节点的值都在 0 - 9 之间那么链表整体就可以代表一个整数。 给定两个这种链表请生成代表两个整数相加值的结果链表。 数据范围 0 ≤ n , m ≤ 1000000 0≤n,m≤1000000 0≤n,m≤1000000链表任意值 0 ≤ v a l ≤ 9 0≤val≤9 0≤val≤9 要求空间复杂度 O ( n ) O(n) O(n)时间复杂度 O ( n ) O(n) O(n)
例如链表 1 为 9-3-7链表 2 为 6-3最后生成新的结果链表为 1-0-0-0。 示例1 输入[9,3,7],[6,3] 返回值{1,0,0,0} 说明如题面解释
示例2 输入[0],[6,3] 返回值{6,3}
备注 1 ≤ n , m ≤ 1 0 6 1≤n,m≤10^6 1≤n,m≤106 0 ≤ a i , b i ≤ 9 0≤ai,bi≤9 0≤ai,bi≤9
解决方案一
1.1 思路阐述
加法运算一般是个位个位相加十位十位相加…。也就是说数据要对位才可以相加就如同题目中给出的加法运算的标准列式计算。
但是对于被加数和加数之间由于它们是由两个链表存储由于两个数之间的位数的大小不一样所以链表存储的节点个数不一样如果按照从左往右的顺序进行运算我们可以看到题目给的图中的情况9和6会相加但是实际上是90060这种位数并不对应。应该执行的操作应该是9000,3060。
但是由于链表最后一个存储的节点一定是个位数往左依次是十位百位所以在链表中我们可以考虑从右往左的顺序但是这与我们所用的加法运算的顺序从左往右相反这时候可以使用链表倒置对于最后的结果再次倒置即为我们所需要的链表。
关于链表倒置参考博客:C/C BM1反转链表
两数相加逢十进一这里我们设置了一个进位carry。
对于节点我们首先判断节点是否为空如果为空则取0值作为运算数据。(这里相当于补0操作) 如果不为空则把节点的值传递给运算值。
1.2 源码
class Solution {public:ListNode* addInList(ListNode* head1, ListNode* head2) {head1 reverseList(head1);head2 reverseList(head2);//添加表头ListNode* res new ListNode(-1);ListNode* head res;int carry 0;while (head1 ! NULL || head2 ! NULL || carry ! 0) {//链表不为空则取其值int val1 head1 NULL ? 0 : head1-val;int val2 head2 NULL ? 0 : head2-val;//相加int temp val1 val2 carry;//获取进位carry temp / 10;temp % 10;//添加元素head-next new ListNode(temp);head head-next;//移动下一个if (head1 ! NULL)head1 head1-next;if (head2 ! NULL)head2 head2-next;}return reverseList(res-next); }ListNode* reverseList(ListNode* head) {if (!head) {return nullptr;}ListNode* pre nullptr;ListNode* current head;while (current) {ListNode* temp current-next;current-next pre;pre current;current temp;}return pre;}
};总结
这道题回顾了一下链表翻转。
对于链表的四则运算涉及到对位情况考虑使用翻转链表会更好。不能按照常规的四则运算从左到右的顺序来做要结合链表本身的特性来做。
