题目链接
结题过程
思路一
用2个数组存储head1和head2的节点数值，然后倒序从两个数组取数值，进行相加，把和存到第三个数组。最够根据第三个数组创建结果链表。
虽然写了出来，但是自我感觉十分蠢笨。用数组就罢了，为什么需要第三个数组？
写了一会想到可以用两个栈来替代数组，间思路二。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
std::vector<int> my_vec1; //把head1的数据存储到数组
std::vector<int> my_vec2; //把head2的数据存储到数组
std::vector<int> my_vec3; //用于输出结果的数组
ListNode* res = nullptr; //用于指向结果链表的头指针
ListNode* cur = head1;
int h1_len = 0, h2_len = 0;
while(cur != nullptr) //把head1的val转移到vector中
{
my_vec1.push_back(cur->val);
cur = cur->next;
}
cur = head2;
while(cur != nullptr) //把head2的val转移到vector中
{
my_vec2.push_back(cur->val);
cur = cur->next;
}
h1_len = my_vec1.size();
h2_len = my_vec2.size();
//确定下面用于计算的循环的次数，也就是输出结果的数组的大小
//因为可能head1和head2最高位的和大于9，会进位，
//所以结果数组的大小要比head1或者head2的成员数量最大值 + 1
int loop = (h1_len > h2_len ? h1_len:h2_len);
loop++;
my_vec3.resize(loop);
//从后往前，依次计算head1和head2成员的和
bool isNeedAdd = false;
for(int i = 0; i < loop; i++)
{
my_vec3[loop - 1 -i] = 0;
int tmp = 0;
//因为head1和head2的成员数量不一定谁多，所以分开加
if(h1_len - 1 - i >= 0)
tmp += my_vec1[h1_len - 1 - i];
if(h2_len - 1 - i >= 0)
tmp += my_vec2[h2_len - 1 - i];
//对相加和的判断：
//情况1: 和大于9，并且有上一次循环的进位
//情况2：和大于9
//情况3：和小于等于9. 并且有上一次循环的进位
//情况4，和小于等于9
if(tmp > 9)
{
tmp = tmp - 10;
if(isNeedAdd) //情况1：保留tmp - 10，并且 + 1
{
tmp++; //9+9最大是18，保留8，再加1也不会大于9了。
isNeedAdd = false;
}
isNeedAdd = true; //情况2：保留tmp - 10，并且向下一个循环进位
}
else
{
if(isNeedAdd) //情况3：给tmp + 1，然后判断是否大于9
{
tmp++;
isNeedAdd = false;
if(tmp > 9)
{
tmp = tmp - 10;
isNeedAdd = true;
}
}
//情况4：无需对tmp处理
}
my_vec3[loop - 1 -i] = tmp; //把和放入结果数组
}
//从结果数组转移到链表
bool is_head = true;
int len3 = my_vec3.size();
for (int i = 0; i < len3; i++)
{
if( i == 0 && my_vec3[i] == 0) //如果结果数组预留的用来进位的最高位没用到，就略过
continue;
if(is_head) //为头指针赋值
{
res = new ListNode(my_vec3[i]);
cur = res;
is_head = false;
continue;
}
cur->next = new ListNode(my_vec3[i]);
cur = cur->next;
}
return res;
}
};
用2个栈来存储head1和head2的值。
然后只要不断出2个栈，再进行求和，创建结果数组的节点就好了。这个步骤一直持续到两个栈都为空。
这样代码明显简洁很多。思路也更清晰。
思路二
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
#include <stack>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
ListNode* ret = nullptr;
ListNode* cur = nullptr;
std::stack<int> s1;
std::stack<int> s2;
bool isNeedPlus = false;
bool isRetHead = true;
cur = head1;
while(cur != nullptr) {
s1.push(cur->val);
cur = cur->next;
}
cur = head2;
while(cur != nullptr) {
s2.push(cur->val);
cur = cur->next;
}
while(!s1.empty() || !s2.empty()) {
int tmp = 0;
if(!s1.empty()) {
tmp += s1.top();
s1.pop();
}
if(!s2.empty()) {
tmp += s2.top();
s2.pop();
}
if(tmp >= 10) {
tmp -= 10;
if(isNeedPlus)
tmp++;
isNeedPlus = true;
}
else {
if(isNeedPlus) {
tmp++;
if(tmp >= 10) {
tmp -= 10;
isNeedPlus = true;
}
else
isNeedPlus = false;
}
else {
isNeedPlus = false;
}
}
cur = new ListNode(tmp);
if(ret == nullptr)
ret = cur;
else {
cur->next = ret;
ret = cur;
}
}
if(isNeedPlus)
{
cur = new ListNode(1);
if(ret == nullptr)
ret = cur;
else {
cur->next = ret;
ret = cur;
}
}
return ret;
}
};
思路三
做到思路二以后，自以为不错。
看到答案后，发现反转链表更牛逼，思路及其清晰，而且任何其余容器都不需要创建。
感觉自己依旧很蠢。
而且获取进位只要判断 【和除以10】 是0还是1就好，我还在那判断是否大于10。
修正后的代码
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
#include <stack>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* ReverseListNode(ListNode* head) { //反转链表
ListNode* rhead = nullptr;
while(head != nullptr) {
ListNode* tmp = head;
head = head->next;
tmp->next = rhead;
rhead = tmp;
}
return rhead;
}
ListNode* addInList(ListNode* head1, ListNode* head2) {
ListNode* ret = nullptr;
head1 = ReverseListNode(head1);//反转链表
head2 = ReverseListNode(head2);//反转链表
int AddNUm = 0;
while(head1 != nullptr || head2 != nullptr)
{
int tmp= 0;
if(head1 != nullptr)
{
tmp += head1->val;
head1 = head1->next;
}
if(head2 != nullptr)
{
tmp += head2->val;
head2 = head2->next;
}
tmp += AddNUm; //因为进位就是加1，所以不管此时tmp是[0,18]中的谁，直接加1
AddNUm = tmp / 10;//判断下一次的进位0或者1
tmp = tmp % 10;//判断当前的值[0,9]
auto cur = new ListNode(tmp);
cur->next = ret;
ret = cur;
}
if(AddNUm == 1) //进位的判断可以整合到上面的while中
{
auto cur = new ListNode(1);
cur->next = ret;
ret = cur;
}
return ret;
}
};
总结
反转链表牛逼。
