leetcode 算法题目学习笔记 - 序号2

2. 两数相加

初始想法

暴力求解，将两个链表里面的数拿出来变成完整数字，求和，再转换为链表倒序存储

点击查看代码

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 tag1{true},tag2{true};bool t1{true},t2{true};bool carry = false;int counts{0};do{int sum{0};tag1 = l1;tag2 = l2;//ptr=ptr->next;if(tag1){sum+=l1->val;t1 = l1->next;l1 = l1->next;}if(tag2){sum+=l2->val;t2 = l2->next;l2 = l2->next;}if(carry){ sum++;   carry = false; }if(sum>9){ sum-=10; carry = true ; }ptr->val=sum;printf("%d ",ptr->val);if((t1||t2)||carry){ptr->next=new ListNode(-1);}if(ptr->next)ptr=ptr->next;std::cout<<std::endl;}while(t1 || t2 || carry); return head;
}
};

解题成功 效果不是很好 还可以进一步优化