题目链接：https://leetcode-cn.com/problems/add-two-numbers-ii/description/
题目描述 给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
【【LeetCode】445. 两数相加 II】你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例 输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
解决方法 分三步：(1)将链表中的数字转化成字符串形式 (2)两个字符串相加 (3)将相加的结果放入链表中
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//分三步：(1)将链表中的数字转化成字符串形式 (2)两个字符串相加 (3)将相加的结果放入链表中string num1,num2;
//(1)将链表中的数字转化成字符串形式
while(l1){
num1+=(l1->val+'0');
l1=l1->next;
}
while(l2){
num2+=(l2->val+'0');
l2=l2->next;
}string result=addStrings(num1,num2);
//(2)两个字符串相加ListNode *head=new ListNode(0);
//(3)将相加的结果放入链表中
ListNode *tail=head;
for (int i=0;
inext=new ListNode(0);
tail->val=(result[i]-'0');
}
return head->next;
}private:
string addStrings(string num1, string num2) {
// 415. 字符串相加
string a=num1,b=num2;
int len=max(a.size(),b.size());
//补零
if (a.size()=1;
i--)
a[i]=a[i-1];
a[0]='0';
}
}
if (b.size()=1;
i--)
b[i]=b[i-1];
b[0]='0';
}
}int add=0;
//进位
string result(len,'0');
for (int i=len-1;
i>=0;
i--){
int temp=(a[i]-'0')+(b[i]-'0');
result[i]=add+temp%10+'0';
add=(result[i]-'0')/10+temp/10;
result[i]=(result[i]-'0')%10+'0';
}
if (add==1){
result+='0';
for (int i=result.size()-1;
i>=1;
i--)
result[i]=result[i-1];
result[0]='1';
}
return result;
}
};
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)