LeetCode. 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

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

C++1

一开始以为很简单，傻傻地先把链表中的元素按照对应位置加起来，然后再从头往后逐个取余重建一个链表即可。但是后来发现链表可以无限延伸，这样即使是long long也存不下这个大的数量级。舍弃这种方法…

class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *head1 = l1, *head2 = l2; if(l1&&!l2){ return l1; } if(!l1&&l2){ return l2; } long long sum = 0, s; long long i = 1, flag = 0; while(head1&&head2){ s = head1->val+head2->val; sum+=i*(((s)+flag)%10); i*=10; if(s>=10){ flag = 1; }else{ flag = 0; } head1 = head1->next; head2 = head2->next; } ListNode* nn = new ListNode(0); ListNode* headn = nn; int v; while(sum!=0){ v = sum%10; ListNode * nd = new ListNode(v); nn->next = nd; nn = nd; sum = sum/10; } return headn->next; } };

C++2

直接从头往后遍历，并实时新增链表节点向新链表后附加节点，节点的value是对应位置两个节点的元素的和%10取余，前提是要知道上一对节点的和是不是大于等于10，如果是，设置flag（默认初始为0）为1，则下一对节点相加后的和要加上flag后再取余。同样也要判断两个节点的和加上flag是否大于等于1。

两支相同长度链表的最后一个节点处如果val1+val2+flag>=10的时候，要新增一个节点附在后面。

需要注意的是有可能两个链表的长度不一样，这时就要另外再处理一下多余的一支链表的元素。当短的链表位置的总和大于等于10的时候，要保留flag的值，加到长链表的第一个节点上，加完之后还要判断是否大于等于10，直到最后剩一支链表且flag=0，那么往后新链表的节点的值就是长链表对应位置的节点的值。

/** * 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 *head1 = l1, *head2 = l2; if(l1&&!l2){ return l1; } if(!l1&&l2){ return l2; } long long sum = 0, s; int flag = 0; ListNode* nn = new ListNode(0); ListNode* headn = nn; while(head1&&head2){ s = head1->val+head2->val; ListNode * nd = new ListNode(((s)+flag)%10); nn->next = nd; nn = nd; if(s+flag>=10){ flag = 1; }else{ flag = 0; } head1 = head1->next; head2 = head2->next; if(!head1&&!head2&&flag == 1){ ListNode * nd2 = new ListNode(1); nn->next = nd2; nn = nd2; } } while(head1){ if(flag == 1){ int va = 1+head1->val; if(va>=10){ flag = 1; }else{ flag = 0; } ListNode * nd3 = new ListNode(va%10); nn->next = nd3; nn = nd3; }else{ nn->next = head1; nn = head1; } head1 = head1->next; if(!head1&&flag == 1){ ListNode * nd5 = new ListNode(1); nn->next = nd5; nn = nd5; } } while(head2){ if(flag == 1){ int va = 1+head2->val; if(va>=10){ flag = 1; }else{ flag = 0; } ListNode * nd4 = new ListNode(va%10); nn->next = nd4; nn = nd4; }else{ nn->next = head2; nn = head2; } head2 = head2->next; if(!head2&&flag == 1){ ListNode * nd6 = new ListNode(1); nn->next = nd6; nn = nd6; } } return headn->next; } };