🤔|LeetCode002|两数相加

Table of Contents

难度：Medium🤔

题目 #

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

思路 #

这道题我做了两次：

后一种方法RE，是因为我采用了前一天使用的数字位数提取的算法，把链表翻译成数字直接运算，导致溢出；
前一种方法，借鉴了CPU中全加器的原理，杜绝了溢出的发生。

代码实现(100%|AC) #

 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) {
        int carry=0,curVal=0,val1,val2;
        bool l1break=false,l2break=false,first=true;
        ListNode* node,*last,*res;
        while(true){
            node=new ListNode;
            if(first)res=node;
            val1=l1==nullptr?0:l1->val;
            val2=l2==nullptr?0:l2->val;
            curVal=val1+val2;
            //cout<<carry<<' ';
            node->val=curVal+carry;
            carry=(node->val>=10);
            if(carry)node->val-=10;
            if(!first)last->next=node;
            last=node;
            first=false;

            //cout<<curVal<<' '<<carry<<endl;

            if(l1!=nullptr)
                l1=l1->next;
            if(l2!=nullptr)
                l2=l2->next;

            if(l1==nullptr&&l2==nullptr)break;

        }

        if(carry==1){
            ListNode* ptr=res;
            while(ptr->next!=nullptr)
                ptr=ptr->next;
            ptr->next=new ListNode(1);
        }
       

        return res;
    }
};

代码实现(99.9%|RE) #

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:

    long long getNumber(ListNode* head){
        long long dec=0,res=0;
        while(head!=nullptr){
            res=res+((long long)pow(10,dec))*head->val;
            if(head->next==nullptr)break;
            head=head->next;
            dec++;
        }
        return res;
    }

    ListNode* convertToList(long long x){
        ListNode* node,* lastNode,* head;
        lastNode=new ListNode(x%10);
        head=lastNode;
        x/=10;
        while(x>0){
            node=new ListNode(x%10);
            lastNode->next=node;
            lastNode=node;
            x/=10;
            // cout<<node->val<<endl;
        }
        return head;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        long long num1,num2;
        num1=getNumber(l1);
        num2=getNumber(l2);
        // cout<<num1<<' '<<num2<<endl;
        return convertToList(num1+num2);
    }
};