2019-10-31 两数相加

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

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

您可以假设除了数字 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;
    }
};