描述
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：0≤n,m≤1000000，链表任意值 0≤val≤9
要求：空间复杂度 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≤a_i ,b_ i ≤9
0≤ai,bi≤9
思路一：
- 把两个链表的元素都添加到两个容器中，并反转这两个链表，根据两个链表的长度的最大值，对长度较小的那个进行补齐。
- 补齐之后对进行运算，创建一个结果容器，如果两个容器的元素的值加起来大于等于10，就让当前值减去10，并加上进制位，插入结果容器，最后如果进制位不等于默认值，就说明还需要把这个进制位也加入结果容器中。
- 结果容器运算结束反转结果容器，并创建虚拟节点，将元素一个一个插入虚拟节点中，最后返回虚拟节点的下一个节点。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
#include <list>
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
// 特殊情况处理：如果两个链表都为空，返回nullptr
if(head1 == nullptr && head2 == nullptr) return nullptr;
// 如果其中一个链表为空，直接返回另一个链表
if(head1 == nullptr) return head2;
if(head2 == nullptr) return head1;
// 将链表数据存到两个容器中
std::vector<int> data1; // 存储链表1的值
std::vector<int> data2; // 存储链表2的值
ListNode* currNode1 = head1; // 遍历链表1的指针
ListNode* currNode2 = head2; // 遍历链表2的指针
// 遍历链表1，将每个节点的值存入data1
while(currNode1 != nullptr)
{
data1.push_back(currNode1->val);
currNode1 = currNode1->next;
}
// 遍历链表2，将每个节点的值存入data2
while(currNode2 != nullptr)
{
data2.push_back(currNode2->val);
currNode2 = currNode2->next;
}
// 反转两个容器，因为链表是从低位到高位存储的，反转后便于从高位开始相加
std::reverse(data1.begin(), data1.end());
std::reverse(data2.begin(), data2.end());
// 确定两个容器的长度，并将较短的容器用0填充到与较长容器相同的长度
int len = 0;
if(data1.size() > data2.size())
{
len = data1.size();
data2.resize(len, 0); // 用0填充data2
}
else
{
len = data2.size();
data1.resize(len, 0); // 用0填充data1
}
// 创建结果容器，用于存储相加后的每一位数字
std::vector<int> res;
int flag = 0; // 进位标志
// 从高位到低位逐位相加
for(int i = 0; i < len; i++)
{
int new_val = data1[i] + data2[i] + flag; // 当前位的和加上进位
if(new_val >= 10) // 如果当前位的和大于等于10，需要进位
{
new_val = new_val - 10; // 当前位的值减去10
flag = 1; // 设置进位标志为1
}
else
{
flag = 0; // 如果不需要进位，重置进位标志
}
res.push_back(new_val); // 将当前位的结果存入结果容器
}
// 如果最后还有进位，将进位添加到结果中
if(flag != 0)
{
res.push_back(flag);
}
// 反转结果容器，使其从低位到高位存储
std::reverse(res.begin(), res.end());
// 创建新的链表来存储结果
ListNode* dummy = new ListNode(0); // 创建一个虚拟头节点
ListNode* currNode = dummy; // 当前节点指针
// 遍历结果容器，创建链表节点
for(int i = 0; i < res.size(); i++)
{
ListNode* newNode = new ListNode(res[i]); // 创建新节点
currNode->next = newNode; // 将新节点连接到当前节点
currNode = currNode->next; // 移动当前节点指针
}
ListNode* resNode = dummy->next; // 获取结果链表的头节点
delete dummy; // 删除虚拟头节点
return resNode; // 返回结果链表的头节点
}
};
思路二：
直接反转两个链表，反转之后进行运算
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
#include <list>
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* reverseList(ListNode* head)
{
// 创建一个前指针
ListNode* prevNode = nullptr;
ListNode* currNode = head;
while(currNode != nullptr)
{
// 暂存下一个节点
ListNode* nextNode = currNode->next;
// 反转当前节点的指针
currNode->next = prevNode;
// 移动prev到当前节点
prevNode = currNode;
// 继续处理下一个节点
currNode = nextNode;
}
// prev最终指向新的头结点
return prevNode;
}
ListNode* addInList(ListNode* head1, ListNode* head2) {
// 特殊情况处理：如果两个链表都为空，返回nullptr
if(head1 == nullptr && head2 == nullptr) return nullptr;
// 如果其中一个链表为空，直接返回另一个链表
if(head1 == nullptr) return head2;
if(head2 == nullptr) return head1;
// 反转两个链表，使其从低位到高位存储
head1 = reverseList(head1);
head2 = reverseList(head2);
// 创建一个虚拟头节点，方便操作
ListNode* dummy = new ListNode(0);
// 当前节点指针，用于构建结果链表
ListNode* currNode = dummy;
// 分别指向两个链表的当前节点
ListNode* currNode1 = head1;
ListNode* currNode2 = head2;
// 进位标志
int flag = 0;
// 遍历两个链表，直到两个链表都为空
while(currNode1 != nullptr || currNode2 != nullptr) {
// 获取当前节点的值，如果链表为空则取0
int val1 = currNode1 != nullptr ? currNode1->val : 0;
int val2 = currNode2 != nullptr ? currNode2->val : 0;
// 计算当前位的和，加上进位
int new_val = val1 + val2 + flag;
// 如果当前位的和大于等于10，需要进位
if(new_val >= 10) {
new_val -= 10; // 当前位的值减去10
flag = 1; // 设置进位标志为1
} else {
flag = 0; // 如果不需要进位，重置进位标志
}
// 创建新节点，存储当前位的值
ListNode* newNode = new ListNode(new_val);
// 将新节点连接到结果链表
currNode->next = newNode;
// 移动当前节点指针
currNode = currNode->next;
// 如果链表1不为空，移动到下一个节点
if (currNode1 != nullptr) currNode1 = currNode1->next;
// 如果链表2不为空，移动到下一个节点
if (currNode2 != nullptr) currNode2 = currNode2->next;
}
// 如果最后还有进位，添加一个新节点
if(flag != 0) {
ListNode* newNode = new ListNode(flag);
currNode->next = newNode;
}
// 获取结果链表的头节点
ListNode* resNode = dummy->next;
// 删除虚拟头节点
delete dummy;
// 反转结果链表，使其从高位到低位存储
resNode = reverseList(resNode);
return resNode;
}
};
