首页 > 编程学习 > 两数相加

两数相加

发布时间:2022/8/24 7:01:44

题目

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

思路

数位大不能化为数相加,直接加就行,这里正好是个位对齐,相对位相加再和前一位的进位相加所得和的商就是进位

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *xhead=new ListNode(0);
        ListNode* p=xhead;
        int len1=0,len2=0;
        ListNode*ll1=l1,*ll2=l2;
        while(ll1){
            len1++;
            ll1=ll1->next;
        }
        while(ll2){
            len2++;
            ll2=ll2->next;
        }
        if(len1<len2)swap(l1,l2),swap(len1,len2);
        int y=0;
        while(l2){
            int sum=l1->val+l2->val+y;
            ListNode*node=new ListNode(sum%10);
            y=sum/10;
            l1=l1->next;
            l2=l2->next;
            p->next=node;
            p=node;
        }
        while(l1){
            int sum=l1->val+y;
            ListNode *node=new ListNode(sum%10);
            y=sum/10;
            l1=l1->next;
            p->next=node;
            p=node;
        }
        if(y){
            ListNode* node=new ListNode(y);
            p->next=node;
        }
        return xhead->next;
    }
};
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号