2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
可用的模板
#include<iostream>
#include<cmath>
// #define A 7
// #define B 4
// int a[A]={9,9,9,9,9,9,9};
// int b[B]={9,9,9,9};
#define A 7
#define B 1
int a[A]={9,9,9,9,9,9,8};
int b[B]={1};
// #define A 3
// #define B 3
// int a[A]={2,4,3};
// int b[B]={5,6,4};
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) {}
};
ListNode* taverse(ListNode *&link){
ListNode* a = link;
for (int i = 0;a != nullptr; i++)
{
std::cout<<a->val<<" ";
if(a->next)
a = a->next;
else break;
}
std::cout<<"\n";
return a;
}
ListNode* createlist(int*array, const int& border){
ListNode* ptr = new ListNode(-1);
ListNode* head = ptr;
for (int i = 0; i < border; i++) {
ptr->val = array[i];
if(i < border-1){
ptr->next = new ListNode;
ptr = ptr->next;
}
}
return head;
}
//-----------
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
return nullntr}
//-----------
int main(){
// ListNode* l1 = new ListNode(2,new ListNode(4,new ListNode(3,nullptr)));
// ListNode* l2 = new ListNode(5,new ListNode(6,new ListNode(4,nullptr)));
ListNode* l1 = createlist(a,A);
ListNode* l2 = createlist(b,B);
taverse(l1);
taverse(l2);
ListNode* result = addTwoNumbers(l1,l2);
std::cout<<std::endl;
taverse(result);
}
初始想法
暴力求解，将两个链表里面的数拿出来变成完整数字，求和，再转换为链表倒序存储
点击查看代码
class Solution {
public:
int turnNumToDigits(long int num, int index){
int digits{0};
long long int buffer = num;
for (int i = 0; i<index ; i++)
{
digits = buffer % 10;
buffer/=10;
}
return digits;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
long long int first{0};
long long int last{0};
long long int solve{0};
for (int i = 0; l1 != nullptr ;i++) {
first += l1->val * pow(10, i);
std::cout<<"Current First: "<<first<<"\n";
l1=l1->next;
}
for (int i = 0;l2 != nullptr; i++) {
last += l2->val * pow(10, i);
std::cout<<"Current Last : "<<last<<"\n";
l2=l2->next;
}
solve = first + last;
std::cout<<"Current solve: "<<solve<<"\n";
ListNode* ptr = new ListNode;
long long int counts{solve};
ListNode* result = ptr;
for (int i = 0;; i++) {
if ((counts/=10)<0.1){
ptr->val = turnNumToDigits(solve,i+1);
break;
}
else{
ptr->next = new ListNode;
ptr->val = turnNumToDigits(solve,i+1);
ptr = ptr->next;
}
//counts++;
std::cout<<counts<<"\n";
}
std::cout<<std::endl;
return result;
}
};
思路很简单 但是简单的令人发笑
因为题目的边缘case给到的最大数字可以达到100位
long long int都存不下
所以必须找到一个办法保证不会溢出，也就是说不能把整个数字都存下来。
或者按照大部分人给的优质解答，他们将两个链表一位一位对比，一个节点一个节点的求和，再把结果存到另一个链表中
中间如果发生进位，就把进位存下来，下一次求和的时候会加上.
点击查看代码
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head=new ListNode(-1);//存放结果的链表
ListNode* h=head;//移动指针
int sum=0;//每个位的加和结果
bool carry=false;//进位标志
while(l1!=NULL||l2!=NULL)
{
sum=0;
if(l1!=NULL)
{
sum+=l1->val;
l1=l1->next;
}
if(l2!=NULL)
{
sum+=l2->val;
l2=l2->next;
}
if(carry)
sum++;
h->next=new ListNode(sum%10);
h=h->next;
carry=sum>=10?true:false;
}
if(carry)
{
h->next=new ListNode(1);
}
return head->next;
}
};
作者：陈乐乐
链接：https://leetcode.cn/problems/add-two-numbers/solutions/4375/liang-shu-xiang-jia-by-gpe3dbjds1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
模仿这个思路：
点击查看代码
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(-1);
ListNode* ptr = head;
bool t1{true},t2{true};
bool carry = false;
int counts{0};
do{
int sum{0};
if(l1){
sum+=l1->val;
t1 = l1->next;
l1 = l1->next;
}
if(l2){
sum+=l2->val;
t2 = l2->next;
l2 = l2->next;
}
if(carry){ sum++; carry = false; }
if(sum>9){ sum-=10; carry = true ; }
ptr->val=sum;
if((t1||t2)||carry){
ptr->next=new ListNode(-1);
}
if(ptr->next)
ptr=ptr->next;
}while(t1 || t2 || carry);
return head;
}
};
解题成功 效果不是很好 还可以进一步优化
标签：ListNode,int,ptr,next,算法,l2,l1,序号,leetcode From： https://www.cnblogs.com/Brakeintime/p/18425415