牛客 - 链表相加(二)

描述
假设链表中每一个节点的值都在 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\le n,m\le 10^6$
$0\le a_i,b_i\le 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) {// 特殊情况处理：如果两个链表都为空，返回nullptrif(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，将每个节点的值存入data1while(currNode1 != nullptr){data1.push_back(currNode1->val);currNode1 = currNode1->next;}// 遍历链表2，将每个节点的值存入data2while(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; // 当前位的值减去10flag = 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) {// 特殊情况处理：如果两个链表都为空，返回nullptrif(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) {// 获取当前节点的值，如果链表为空则取0int 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; // 当前位的值减去10flag = 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;}
};