2.两数相加
题目说明
给出两个 非空 的链表用来表示两个非负的整数，其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除数字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) {
}
}
开始的思路：：
同时遍历两个链表，获取两个链表对应结点的值val，取和后作为要返回的新的链表的对应结点的val，要注意的是，val要判断是否超过了10，假如超过了10要进行进位。当发现两个链表指向都为空的时候，结束遍历，返回新的链表。
思路中的错误：
1.首先既然val要判断是否超过了10，可以发生进位，那么在进行计算的时候应该将两个链表的值和count进位的值的和作为新的链表的对应的val。
2.其次，当发现两个链表皆为空时结束循环也是错误的，因为假如存在进位'count = 1'，那么结束循环，这个count直接不存在的了，所以还要判断count的值是否为0，来作为遍历结束的标志。
3.（这点谈不上是错误，像是不知道的总结）首先是关于结构体的定义，可以这样写ListNode *head = new ListNode(-1),同样的，定义变量也可以是int a(0)，这些是我以前是不知道的。
4.还有在提交的时候，给出了这样一个例子
输入：0,0
输出: 0
虽然题目写着两个链表都不以0开头，但是还是给出这样的一个例子，为了得到正确的结果，所以我将while结束的判定条件移到了开始的部分，不再检测p -> next是否为NULL，而是检测p是否为NULL。
提交代码：
/**
* 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 *p,*q,*g;
ListNode *l3 = new ListNode(-1);
p = l1;
q = l2;
g = l3;
int num1, num2;
num1 = num2 = 0;
int sum = 0;
int count = 0;
bool flag = true;
while(flag){
if(p == NULL && q == NULL){
if(count == 0){
flag = false;
break;
}
}
if(p != NULL){
num1 = p -> val;
p = p -> next;
}
if(q != NULL){
num2 = q -> val;
q = q -> next;
}
if((num1 + num2 + count) < 10){
sum = num1 + num2 + count;
count = 0;
}
else{
sum = num1 + num2 + count- 10;
count = 1;
}
num1 = num2 = 0;
g -> next = new ListNode(sum);
g = g -> next;
}
g -> next = NULL;
return l3->next;
}
};
还有一种思路是让两个链表长度保持一致，较短的那一个进行补零的操作，明天我看明白了再补上。
whitor0428于2020/07/28
喜欢可以点赞
欢迎评论