LeetCode2. 两数相加

写在前面：

题目链接：LeetCode2两数相加
编程语言：C++
题目难度：中等

一、题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

二、题目分析&解题思路&代码实现

2.1 常规老实人解法

解之前先吐槽一番，计算两个数相加的结果，给个单向链表也就算了，存的还是数字的反序，意味着本来要计算，123+23，还得
先将链表遍历一遍：

3->2->1
3->2

再反序一次得到正序 (后面才意识到不用反序)

1，2 ，3
2，3

接下来就开始进行
加法运算

要么先将 1，2 ，3 和2，3 先转换为 123、23 ，然后计算得出结果为 146，然后再逐一的进行再把每一位取出来，并且按照逆序 构建成 一个 6->4->1 单向链表再返回回去；

要么直接进行按位相加，自己设计进位，最后 组成 6，4，1 这样有一个序列然后构建链表，再返回。

各位献丑了，且看我写了半小时的代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* listResult = new ListNode();vector<int> vct1;vector<int> vct2;ListNode* nodeTemp = l1;//先将l1、l2遍历一遍while(nodeTemp != nullptr){vct1.push_back(nodeTemp->val);nodeTemp = nodeTemp->next;}ListNode* nodeTemp1 = l2;while(nodeTemp1 != nullptr){vct2.push_back(nodeTemp1->val);nodeTemp1 = nodeTemp1->next;}vector<int> vctResult;int i = 0;int j = 0;int iTemp = 0;bool isTen = false;//是否进位//开始按位相加 从 个位开始while(i<vct1.size() && j<vct2.size()){iTemp = vct1[i] + vct2[j];if(isTen){iTemp +=1;}if(iTemp >= 10){isTen = true;iTemp = iTemp -10;}   else{isTen = false;}      vctResult.push_back(iTemp);i++;j++;}//两个链表长度不相等，那么剩下的直接继续按位加即可while( i <vct1.size()){if(isTen)//注意上一个while 后可能还有进位 1{if(vct1[i] + 1 ==10)//继续进位{vctResult.push_back(0);isTen = true;}else{vctResult.push_back(vct1[i]+1);isTen = false;}i++;}else{//没有进位直接插入即可vctResult.push_back(vct1[i]);i++;}}//同理将剩下的都插入，和上面进位机制一样while( j< vct2.size()){if(isTen){if(vct2[j] + 1 ==10){vctResult.push_back(0);isTen = true;}else{vctResult.push_back(vct2[j]+1);isTen = false;}j++;}else{vctResult.push_back(vct2[j]);j++;}}if(isTen)//注意可能最后还有一次进位{vctResult.push_back(1);}//接下来构建出链表bool head = true;ListNode* nodenext = new ListNode();for(int k = 0; k < vctResult.size();k++){ListNode* node = new ListNode();node->val = vctResult[k];node->next = nullptr;if(head){listResult = node;//保存头，做返回值返回nodenext = node;head = false;}else{nodenext->next = node;nodenext = nodenext->next;}}return listResult;}
};

运行结果：
跑了几次好一点的就是下面这样了

2.1.2 优化后

写道最后，才发现不需要用两个vector 遍历，直接遍历链表即可，我们常固性思维觉得加法就是这样：

其实我们做个镜像对比：

这不就是我们刚好要的答案吗？
因此我们现在直接简化为：
遍历两个链表

3 -> 2 -> 1
3->2

将刚才的代码额外的两次遍历与两个vector 开辟 干掉：

直接做进位的加法，我们将上述的代码优化为：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* listResult = new ListNode();ListNode* nodeTemp = l1;ListNode* nodeTemp1 = l2;vector<int> vctResult;int i = 0;int j = 0;int iTemp = 0;bool isTen = false;//是否进位//开始按位相加 从 个位开始while(nodeTemp!=nullptr && nodeTemp1!=nullptr){iTemp = nodeTemp->val + nodeTemp1->val;if(isTen){iTemp +=1;}if(iTemp >= 10){isTen = true;iTemp = iTemp -10;}   else{isTen = false;}      vctResult.push_back(iTemp);nodeTemp = nodeTemp->next;nodeTemp1 = nodeTemp1->next;}//两个链表长度不相等，那么剩下的直接继续按位加即可while( nodeTemp!= nullptr){if(isTen)//注意上一个while 后可能还有进位 1{if(nodeTemp->val + 1 ==10)//继续进位{vctResult.push_back(0);isTen = true;}else{vctResult.push_back(nodeTemp->val+1);isTen = false;}nodeTemp=nodeTemp->next;}else{//没有进位直接插入即可vctResult.push_back(nodeTemp->val);nodeTemp=nodeTemp->next;;}}//同理将剩下的都插入，和上面进位机制一样while( nodeTemp1 != nullptr){if(isTen){if(nodeTemp1->val + 1 ==10){vctResult.push_back(0);isTen = true;}else{vctResult.push_back(nodeTemp1->val+1);isTen = false;}nodeTemp1 = nodeTemp1->next;}else{vctResult.push_back(nodeTemp1->val);nodeTemp1 = nodeTemp1->next;}}if(isTen)//注意可能最后还有一次进位{vctResult.push_back(1);}//接下来构建出链表bool head = true;ListNode* nodenext = new ListNode();for(int k = 0; k < vctResult.size();k++){ListNode* node = new ListNode();node->val = vctResult[k];node->next = nullptr;if(head){listResult = node;//保存头，做返回值返回nodenext = node;head = false;}else{nodenext->next = node;nodenext = nodenext->next;}}return listResult;}
};

可以看到时间和空间上都有所优化。

但是可以看到整个代码还是臭长臭长的，而且还开辟了一个新vector用于保存结果，空间复杂度也没有降低，还有没有更简介的写法呢？

2.3 写法简化&空间优化

之前还需要一个 bool 值来控制是否进位，每次还需要取余数等等，非常的繁琐

其实我们直接取两位和的个位数，为当前位的值，取 10 位上的数为进位即可
例如 5 + 9，

当前位为 14 % 10 = 4；
进位为：14 / 10 = 1;

而且之前会考虑链表长度不相等的情况，然后对余下的节点再做一次遍历，并且判断之前的进位：

换种思路，我们将空缺的部分补 上 0

这样来处理长度不一样的情况：

        int n1 = nodeTemp == nullptr ? 0: nodeTemp->val;int n2 = nodeTemp1 == nullptr ? 0:nodeTemp1->val;

完整代码示例：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* head = nullptr;ListNode* tail = nullptr;ListNode* nodeTemp = l1;ListNode* nodeTemp1 = l2;int igientle = 0;//进位//开始按位相加 从 个位开始while(nodeTemp!=nullptr || nodeTemp1!=nullptr){//链表长度不够时补 0 ，int n1 = nodeTemp == nullptr ? 0: nodeTemp->val;int n2 = nodeTemp1 == nullptr ? 0:nodeTemp1->val;int temp = n1+n2+igientle;//两位的和再加上进位if(!head)//先将头节点保存好{head = new ListNode(temp % 10);//取余数tail = head;}  else{tail->next = new ListNode(temp%10);tail = tail->next;}igientle=temp/10;//进位   if(nodeTemp){nodeTemp = nodeTemp->next;}if(nodeTemp1){nodeTemp1 = nodeTemp1->next;}}if(igientle > 0)//最后还有进位时也加上{tail->next = new ListNode(igientle);}return head;}
};

运行结果：