最详解——两数相加

链表相加+处理进位

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

思路解析

先提取关键信息：两个整数，非负，逆序存储，按位存储，实现不同位数相加

首先分析程序流程应当如下：

因为题目只让写核心算法，所以这里只写核心算法，即addTwoNumbers()函数，其余数据处理请详见代码

1. 考虑到两个链表的数字位数可能不一样，而运算是否停止取决于位数大的数字，因此在做相加时，判断条件为两个链表任意一个不为空，则运算继续
2. 对于123+123这种，不需要考虑进位，而像123+996这种，需要考虑进位的问题，因此在做相加时，判断条件为进位是否为0，因此应该设置一个变量carry记录进位

从而得出限制条件为 l1 != 0 || l2 != 0 || carry != 0

在此条件下逐位相加，每加一次，就将结果放入result节点，但是直接放不行，因为sum = 7+8 = 15，每个节点只能存储一位数字，因此利用sum%10记录进位后个位上的数，利用sum/10向carry传递进位数据，最终将结果存入新链表并返回

代码：

#include using namespace std;//节点类
class ListNode
{
public:int val;ListNode *next;ListNode() {}ListNode(int x):val(x),next(nullptr) {}ListNode* Insert(string str,ListNode *l){ListNode *s,*r = l;for(auto &x : str){if(isdigit(x)){s = new ListNode();s->val=x-'0';r->next=s;r=s;}}r->next = NULL;return l;}
};
//核心算法类
class Solution
{
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){ListNode *tmp = nullptr;ListNode *result = nullptr;int carry = 0;while(l1 != nullptr || l2 != nullptr ||carry != 0){int sum = (l1 == nullptr ? 0:l1->val) + (l2 == nullptr ? 0:l2->val) + carry;carry = sum/10;ListNode *node = new ListNode(sum%10);if(tmp == nullptr){tmp = node;result = tmp;}else{tmp->next = node;tmp = tmp->next;}l1 = l1 == nullptr ? nullptr:l1->next;l2 = l2 == nullptr ? nullptr:l2->next;}return result;}
};
//按照 + 将字符串分割为两部分
vector split(const string &str, const string &pattern)
{vector res;if(str == "")return res;string strs = str + pattern;size_t pos = strs.find(pattern);while(pos != strs.npos){string temp = strs.substr(0, pos);res.push_back(temp);strs = strs.substr(pos+1, strs.size());pos = strs.find(pattern);}return res;
}int main()
{char s[1000];cin.getline(s,50);vector result = split(s,"+");ListNode *l1 = new ListNode();l1->Insert(result[0],l1);ListNode *l2 = new ListNode();l2->Insert(result[1],l2);Solution Sve;ListNode *res = Sve.addTwoNumbers(l1->next,l2->next);cout<val<<" -> "<next->val<<" -> "<next->next->val;return 0;
}

Sve.addTwoNumbers(l1->next,l2->next);

cout<val<<" -> "<next->val<<" -> "<next->next->val;
return 0;

}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！