题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

思路1

• 通过所有种可全部写出来跑代码，结果发现内存超出了限制（还是第一次遇到这种情况），感觉上是在考虑解题时可能分类讨论的情况过于重复，陷入了死循环

/*** 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* res = new ListNode(0);ListNode* cur = res;ListNode* pre = NULL;int carry = 0;while(l1 != NULL && l2 != NULL){cur -> val = l1 -> val + l2 ->val + carry;carry = cur -> val /10;cur -> val = cur -> val % 10;cur -> next = new ListNode(0);pre = cur;cur = cur -> next;l1 = l1 -> next;l2 = l2 -> next;    }while(l1 != NULL){cur -> val = l1 -> val  + carry;carry = cur -> val /10;cur -> val = cur -> val % 10;cur -> next = new ListNode(0);pre = cur;cur = cur -> next;l1 = l1 -> next;}while(l2 != NULL){cur -> val = l2 -> val  + carry;carry = cur -> val /10;cur -> val = cur -> val % 10;cur -> next = new ListNode(0);pre = cur;cur = cur -> next;l1 = l2 -> next;}if(carry == 0){pre -> next = NULL;}else{cur -> val = carry;}return res;}
};

思路2

• 通过题解看了看别人的代码，改进了一下，用原始方法处理了进位的问题，代码如下：

/*** 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 n1,n2,n3;// 初始化进位符为0int c = 0;ListNode* r = NULL;ListNode* current = NULL;while(l1!= NULL || l2!= NULL){// 取数操作if (l1 == NULL){n1 = 0;}else {n1 = l1 -> val;l1 = l1 -> next;}if (l2 == NULL){n2 = 0;}else {n2 = l2 -> val;l2 = l2 -> next;}// 当前位两个数相加的和，带上进位符cn3 = n1+n2+c;// 相加完成，进位符归0c = 0;// 若每位的两个数相加的和大于9，则，c=1if (n3 > 9){n3 %= 10;c = 1;}// 存数操作if (r == NULL) {r = new ListNode(n3);current = r;} else {current -> next = new ListNode(n3);current = current -> next;}}// 最后如果输入的两个ListNode都遍历完了，但是进位符c还为1，说明需要再进一位，则在返回的r后再添加1if (c == 1){current -> next = new ListNode(1);}return r;}
};