美文网首页
2. 两数相加(C++)

2. 两数相加(C++)

作者: codehory | 来源:发表于2019-07-31 13:03 被阅读0次

    给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储一位数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

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

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

    思路

    • 将两个链表看成是等长的链表相加,不足位的补0,例如:75+6,看成75+06
    • 每一位计算的要考虑上一位的进位问题,并缺当前位计算结束后同样需要更新进位值
    • 两个链表各位相加完之后,如果最后的进位值为1,需要在链表上添加一个新的结点(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* pre=new ListNode(0);
            ListNode* cur=pre;
            ListNode* p1=l1,*p2=l2;
            int carry=0;                     //进位值
            while(p1!=NULL||p2!=NULL){
                int x=(p1!=NULL)?p1->val:0;  //此位若为空,则补0
                int y=(p2!=NULL)?p2->val:0;  //此位若为空,则补0
                int sum=x+y+carry;
                cur->next=new ListNode(sum%10);
                carry=sum/10;
                cur=cur->next;
                if(p1!=NULL)
                    p1=p1->next;
                if(p2!=NULL)
                    p2=p2->next;
            }
            if(carry>0)
                cur->next=new ListNode(carry); //添加结点1
            return pre->next;
        }
    
        void printList(ListNode* l1){
            ListNode* p=l1;
            while(p!=NULL){
                cout<<p->val<<" ";
                p=p->next;
            }
        }
    
    };
    
    int main() {
        std::cout << "Hello, World!" << std::endl;
        ListNode* s1=new ListNode(5);
        s1->next=new ListNode(7);
        ListNode* s2=new ListNode(6);
        Solution s;
        s.printList(s.addTwoNumbers(s1,s2));
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:2. 两数相加(C++)

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