分类信息有哪些网站,金融理财管理网站源码 dedecms,wordpress根据id排序,一键生成app的软件描述 假设链表中每一个节点的值都在 0 - 9 之间#xff0c;那么链表整体就可以代表一个整数。 给定两个这种链表#xff0c;请生成代表两个整数相加值的结果链表。 数据范围#xff1a;0≤n,m≤1000000#xff0c;链表任意值 0≤val≤9 要求#xff1a;空间复杂度 O(n)那么链表整体就可以代表一个整数。 给定两个这种链表请生成代表两个整数相加值的结果链表。 数据范围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) {// 特殊情况处理如果两个链表都为空返回nullptrif(head1 nullptr head2 nullptr) return nullptr;// 如果其中一个链表为空直接返回另一个链表if(head1 nullptr) return head2;if(head2 nullptr) return head1;// 将链表数据存到两个容器中std::vectorint data1; // 存储链表1的值std::vectorint 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::vectorint 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;}
};
