题目
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解法一(我的思路)
思路：
将两个链表代表的数字给表示出来，再将其求和，将将求和结果按照逆序的链表形式输出即可！
/**
* 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) {
// 先计算出两个链表之间所代表的之和
int sum = 0;
int temp_i=1;
ListNode *temp = l1;
do{
sum += temp->val*temp_i;
temp_i = temp_i*10;
temp = temp->next;
}while(temp!=NULL);
temp = l2;
temp_i = 1;
do{
sum += temp->val*temp_i;
temp_i = temp_i*10;
temp = temp->next;
}while(temp!=NULL);
// 计算完成求和 开始创建新的链表 用来存放新的数据
ListNode * p = new ListNode(0);
ListNode * q;// 用来移动新生成的链表
q = p;
int num = 0;
num = sum % 10;
sum = sum / 10;
p->val = num;
do{
ListNode *newNode = new ListNode(0); // 创建新的节点
if(sum>0) break;
int num = 0;
num = sum % 10;
sum = sum / 10;
// 给临时节点赋值
newNode->val = num;
newNode->next = NULL;
q->next = newNode; //将临时节点赋值给移动的链表(指向新的链表)
q = newNode; // 此时移动的链表需要移动到当前节点上来
}while(sum>0);
return p;
}
};
在执行代码上计算结果与预期的结果一致，但是提交代码时，老是提示错误？ 我开始绝望了。执行代码的时间4ms，但是提交结果会出现错误？
错误提示为：
Line 28: Char 29: runtime error: signed integer overflow: 1000000000 * 9 cannot be represented in type 'int' (solution.cpp)
始终没有找到错误的原因？ 但是觉得自己的思路是对的！ 所以就没有纠结这个问题，查看评论中网友给的答案？
解法二(自己的思路二)
思路：
由于对于该数据表示的单链表而言，其表示的第一个数字代表整数的个位数，其表示的第二位代表整数的十位数，以此类推。。。
同理另外一个数也是这样表示的，所以当两个数字相加时，就是个位相加，遇到大于10，进一位即可，即可以在对链表遍历的同时计算出最终的结果。
(需要考虑两个链表不一样长的问题！)
/**
* 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)
{
ListNode *result = new ListNode(0); //存放结果的链表
ListNode *p1 ,*p2; //分别指向两个相加的链表
ListNode *temp ; // 临时节点 存放临时数据
temp = result;
p1 = l1 , p2 = l2;
int z = 0; // 用来表示最终相同位数求和有没有超过10的
while(p1!=NULL || p2!=NULL){ //当两个指针都为空跳出来(思想差不多 不过后面参考了答案)
// 用这种方式可以避免其判断 两个链表之间的长度问题 当一个链表到头了，用0表示后面位数
int x = (p1!=NULL) ? p1->val : 0 ;
int y = (p2!=NULL) ? p2->val : 0 ;
if(p1) p1 = p1->next;
if(p2) p2 = p2->next;
int sum = z + x+y;
z = sum /10; // 用来记录大于10的位数(进一位则会记录下来)
temp->next = new ListNode( sum % 10 );
temp = temp->next;
}
// 当两者都已经为空 看最后一位有没有超过10的值
if(z>0) temp->next = new ListNode(z);
return result->next;
}
};
与答案的思想相同，但好像最后有参考答案怎么写的，虽然用的是java语言，因为觉得他写的会比我自己写的更简洁一点，但是后面还是尽量少的参考答案吧！！！！
中间有发现出现错误是，时间超时，后面检查发现代码错误！！ 所以一般不会出现超时的现象！
结果： 时间 40ms 97.14%. 内存 19.2M 37.42%
解答三 (网友答案1)
使用了递归的思想，效率挺高的！
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
return addByBit(l1, l2, 0);
}
ListNode* addByBit(ListNode* l1, ListNode* l2, int carry) {
if (l1 == NULL) l1 = new ListNode(0);
if (l2 == NULL) l2 = new ListNode(0);
ListNode *l = new ListNode((l1->val + l2->val + carry) % 10);
carry = (l1->val + l2->val + carry) / 10;
if(l1->next != NULL || l2->next != NULL || carry == 1) {
l->next = addByBit(l1->next, l2->next, carry);
}
return l;
}
};
时间： 40ms
内存: 19.6M
解答四 (网友答案2)
主要的套路跟我第二个套路是一样的。
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *ans = new ListNode(0), *t1=l1, *t2=l2;
ListNode *anshead=ans;
int carry=0;
while(t1||t2){
if(t1){
carry+= t1->val;
t1 = t1->next;
}
if(t2){
carry+= t2->val;
t2 = t2->next;
}
ans->val = carry%10;
carry /= 10;
if(t1||t2||carry){
ans->next = new ListNode(carry);
ans = ans->next;
}
}
return anshead;
}
};
时间：44ms
内存： 19.2M
问题：
使用链表的操作不太熟悉，对链表的使用掌握的不够！
学习链表知识:
链表主要包括两个方面:
数据域 和 指针域
- 单链表节点信息包括:
-
数据域 : 用于存储数据元素的值
-
指针域(链域)： 用于存放下一个节点地址或者指向后面节点的指针
struct Node{
int val; //数据域
Node *next; //指针域
}
具体参考链接...
参考链接:
网友评论