欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode-2 两数相加

程序员文章站 2022-06-26 08:48:17
...

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

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

示例:

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

这道题由于涉及到大数(标准数据类型表示不了),所以我们不能将两个数转换为整数类型相加再转化为字符串后逐一添加到链表中返回。

我的方法十分简单粗暴(惭愧)。。。我先定义了两个vector<int>数组sum1和sum2,将两个链表一一导入到数组中去(为什么使用vector呢,因为vector的动态特性让我们无需知道两个链表的长度,且易于获取自身长度)。为了方便起见,我们用vector自带的swap函数将较长的数组表示为sum1,以便于将较短的数组的各项一一加到较长的数组对应项上去。完成这一步后,我用for循环遍历sum1,将每一项超过10的数据减去10并在下一位加上1,若最后一位大于10,则先用if判断i=sum1.size()后先用push_back在最后一项之后添加一个0,再进行上位的工作。完成后,我们就得到了用vector数组储存的结果,最后我们创建一个新的链表并将sum1的数据一一导入之后返回该链表即可。

代码如下:

/**
 * 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) {
        vector<int>sum1;
        vector<int>sum2;
        ListNode *p1=l1;
        ListNode *p2=l2;
        while(1){
            sum1.push_back(p1->val);
            if(p1->next==NULL){
                break;
            }
            p1=p1->next;
        }
        while(1){
            sum2.push_back(p2->val);
            if(p2->next==NULL){
                break;
            }
            p2=p2->next;
        }
        if(sum1.size()<sum2.size()){
            sum1.swap(sum2);
        }
        int i=0;
        for(i=0;i<sum2.size();i++){
            sum1[i]+=sum2[i];
        }
        i=0;
        for(i=0;i<sum1.size();i++){
            if(sum1[i]>=10){
                if(i==sum1.size()-1){sum1.push_back(0);}
                sum1[i]-=10;
                sum1[i+1]++;
            }
        }
        ListNode *l3=new ListNode(-1);
        ListNode *p3=l3;
        for(i=0;i<sum1.size();i++){
            p3->val=sum1[i];
            if(i==sum1.size()-1){break;}
            p3->next=new ListNode(-1);
            p3=p3->next;
        }
        return l3;
    }
};