美文网首页LeeCode题目笔记
2019-10-31 两数相加

2019-10-31 两数相加

作者: Antrn | 来源:发表于2019-10-31 21:18 被阅读0次

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

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

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

    相关文章

      网友评论

        本文标题:2019-10-31 两数相加

        本文链接:https://www.haomeiwen.com/subject/zwqxbctx.html