LeetCode第2题-两数相加（C++实现）

大家好，我是一只学弱狗，记录学习的点点滴滴！
算法才是程序设计的灵魂，每日一题！

优质文章
  • 一张黄图的故事
  • JavaSE练习项目
  • 我是菜鸟、我小试牛刀
  • linux指令太多记不住？小白看这篇就够了！
优质专栏
  • 数据库就该这样学
  • 爪哇外步篇


刚看到的时候觉得挺难的，因为数据结构忘光了，但是通过不断的尝试，发现其实挺简单的，我大概说下思路吧
首先如果你会求解两个整数相加，那么这道题你就已经成功了一多办了，什么？两个整数相加？这不分分中，哈哈哈，其实我的意思是两个超级长的整数相加，意味着，你是用long long 类型也是保存不下的，那么这该怎么做呢？我们可以使用两个字符串来代表这两个超级长的数，然后将它们反转，即低位对齐，然后进行各位相加和进位，待结束后再将字符串反转，即为两树的和，下面是这部分代码的实现

string strAdd(string a,string b){string result="";int len = min(a.length(),b.length());int jinwei = 0;int i;for(i=0;i<len;i++){int temp = charToInt(a[i])+charToInt(b[i])+jinwei;result.push_back(intToChar(temp%10));jinwei = temp/10;}while(i<a.length()){int temp = charToInt(a[i])+jinwei;result.push_back(intToChar(temp%10));jinwei = temp/10;i++;}while(i<b.length()){int temp = charToInt(b[i])+jinwei;result.push_back(intToChar(temp%10));jinwei = temp/10;i++;}if(jinwei!=0){result.push_back(intToChar(jinwei));}return result;
}

这里面用到了两个小函数、int到char，char到int，还是很好用的,下面是它们的实现，如果大家有好的API可以留言，感激不尽！

int charToInt(char c){return c-'0';
}
char intToChar(int i){return '0'+i;
}

如果你会求解上面这个问题的话，你会发现这题考的不就是这么？你都不需要反转，因为链表自己就是反的，也就是说，你只需要读取链表中的各个值，拼成字符串，然后两个字符串相加，将得到的结果转为一个单链表就完事了，怎么样，是不是很简单，你快去试试吧！
下面附上我的devcpp的代码，因为刚开始遇到了不少问题，网页里面执行起来真的慢！

#include <iostream>
#include <sstream>
#include <string>using namespace std;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) {}
};//string reverse(string str){
//	if(str.length()==1) return str;
//	return str[str.length()-1]+reverse(str.substr(0,str.length()-1)); 
//}int charToInt(char c){return c-'0';
}
char intToChar(int i){return '0'+i;
}ListNode* createListNode(string num){int len = num.length();if(len>0){ListNode* head = new ListNode(charToInt(num[0]));ListNode* front = head;ListNode * tmp = NULL;for(int i=1;i<len;i++){tmp = new ListNode(charToInt(num[i]));front->next = tmp;front = tmp;}return head;}	return NULL;
}string strAdd(string a,string b){string result="";int len = min(a.length(),b.length());int jinwei = 0;int i;for(i=0;i<len;i++){int temp = charToInt(a[i])+charToInt(b[i])+jinwei;result.push_back(intToChar(temp%10));jinwei = temp/10;}while(i<a.length()){int temp = charToInt(a[i])+jinwei;result.push_back(intToChar(temp%10));jinwei = temp/10;i++;}while(i<b.length()){int temp = charToInt(b[i])+jinwei;result.push_back(intToChar(temp%10));jinwei = temp/10;i++;}if(jinwei!=0){result.push_back(intToChar(jinwei));}return result;
} 
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {stringstream ss;string s1 = "",s2 = "";while(l1!=NULL){s1.push_back(intToChar(l1->val));l1 = l1->next;}while(l2!=NULL){s2.push_back(intToChar(l2->val));l2 = l2->next;}string result = strAdd(s1,s2);     return createListNode(result);
}int main(){ListNode* l1 = createListNode("1000000000000000000000000000001");ListNode* l2 = createListNode("564");ListNode* result = addTwoNumbers(l1,l2);while(result!=NULL){cout<<result->val;result = result->next;}return 1;
}

下面是提交给力扣的代码

/*** Definition for singly-linked list.* 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) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {stringstream ss;string s1 = "",s2 = "";while(l1!=NULL){s1.push_back(intToChar(l1->val));l1 = l1->next;}while(l2!=NULL){s2.push_back(intToChar(l2->val));l2 = l2->next;}string result = strAdd(s1,s2);     return createListNode(result);}int charToInt(char c){return c-'0';}char intToChar(int i){return '0'+i;}string reverse(string str){if(str.length()==1) return str;return str[str.length()-1]+reverse(str.substr(0,str.length()-1)); }ListNode* createListNode(string num){int len = num.length();if(len>0){ListNode* head = new ListNode(charToInt(num[0]));ListNode* front = head;ListNode * tmp = NULL;for(int i=1;i<len;i++){tmp = new ListNode(charToInt(num[i]));front->next = tmp;front = tmp;}return head;}	return NULL;}string strAdd(string a,string b){string result="";int len = min(a.length(),b.length());int jinwei = 0;int i;for(i=0;i<len;i++){int temp = charToInt(a[i])+charToInt(b[i])+jinwei;result.push_back(intToChar(temp%10));jinwei = temp/10;}while(i<a.length()){int temp = charToInt(a[i])+jinwei;result.push_back(intToChar(temp%10));jinwei = temp/10;i++;}while(i<b.length()){int temp = charToInt(b[i])+jinwei;result.push_back(intToChar(temp%10));jinwei = temp/10;i++;}if(jinwei!=0){result.push_back(intToChar(jinwei));}return result;} 
};