leetcode 算法题目学习笔记 - 序号2

Brakeintime / 2024-09-23 / 原文

2. 两数相加

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

可用的模板

#include<iostream>
#include<cmath>

// #define A 7
// #define B 4
// int a[A]={9,9,9,9,9,9,9};
// int b[B]={9,9,9,9};

#define A 7
#define B 1
int a[A]={9,9,9,9,9,9,8};
int b[B]={1};

// #define A 3
// #define B 3
// int a[A]={2,4,3};
// int b[B]={5,6,4};

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) {}
  };


    ListNode* taverse(ListNode *&link){
        ListNode* a = link;
        for (int i = 0;a != nullptr; i++)
        {
            std::cout<<a->val<<" ";
            if(a->next)
                a = a->next;
            else break;
        }
        std::cout<<"\n";
        return a;
        
    }




    ListNode* createlist(int*array, const int& border){
        ListNode* ptr = new ListNode(-1);
        ListNode* head = ptr;
        for (int i = 0; i < border; i++) {

                ptr->val = array[i];
                if(i < border-1){

                    ptr->next = new ListNode;
                    ptr = ptr->next;
                
                }
        }
        return head;
    }
//-----------
     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  return nullntr}
//-----------

int main(){
    // ListNode* l1 = new ListNode(2,new ListNode(4,new ListNode(3,nullptr)));
    // ListNode* l2 = new ListNode(5,new ListNode(6,new ListNode(4,nullptr)));
    ListNode* l1 = createlist(a,A);
    ListNode* l2 = createlist(b,B);
    taverse(l1);
    taverse(l2);
    ListNode* result = addTwoNumbers(l1,l2);
    std::cout<<std::endl;
    taverse(result);
}

初始想法

暴力求解，将两个链表里面的数拿出来变成完整数字，求和，再转换为链表倒序存储

点击查看代码

class Solution {
public:
                int turnNumToDigits(long int num, int index){
        int digits{0};
        long long int buffer = num;
        for (int i = 0; i<index ; i++)
        {
            digits = buffer % 10;
            buffer/=10;
        }
        return digits;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        long long int first{0};
        long long int last{0};
        long long int solve{0};
        for (int i = 0; l1 != nullptr ;i++) {

            first += l1->val * pow(10, i);
            std::cout<<"Current First: "<<first<<"\n";
            l1=l1->next;


        }
        for (int i = 0;l2 != nullptr; i++) {

            last += l2->val * pow(10, i);
            std::cout<<"Current Last : "<<last<<"\n";
            l2=l2->next;

        }
        solve = first + last;
        std::cout<<"Current solve: "<<solve<<"\n";
        ListNode* ptr = new ListNode;
        long long int counts{solve};
        ListNode* result = ptr;
        for (int i = 0;; i++) {
            if ((counts/=10)<0.1){
                ptr->val = turnNumToDigits(solve,i+1);
                break;
            }
            else{
                ptr->next = new ListNode;
                ptr->val = turnNumToDigits(solve,i+1);
                ptr = ptr->next;
            }
            //counts++;
        std::cout<<counts<<"\n";
        }

        std::cout<<std::endl;
        return result;
    
    }
};

思路很简单但是简单的令人发笑
因为题目的边缘case给到的最大数字可以达到100位
long long int都存不下
所以必须找到一个办法保证不会溢出，也就是说不能把整个数字都存下来。
或者按照大部分人给的优质解答，他们将两个链表一位一位对比，一个节点一个节点的求和，再把结果存到另一个链表中
中间如果发生进位，就把进位存下来，下一次求和的时候会加上.

点击查看代码

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head=new ListNode(-1);//存放结果的链表
        ListNode* h=head;//移动指针
        int sum=0;//每个位的加和结果
        bool carry=false;//进位标志
        while(l1!=NULL||l2!=NULL)
        {
            sum=0;
            if(l1!=NULL)
            {
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2!=NULL)
            {
                sum+=l2->val;
                l2=l2->next;
            }
            if(carry)
                sum++;
            h->next=new ListNode(sum%10);
            h=h->next;
            carry=sum>=10?true:false;
        }
        if(carry)
        {
            h->next=new ListNode(1);
        }
        return head->next;
    }
};

作者：陈乐乐
链接：https://leetcode.cn/problems/add-two-numbers/solutions/4375/liang-shu-xiang-jia-by-gpe3dbjds1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

模仿这个思路：

点击查看代码

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* head = new ListNode(-1);
    ListNode* ptr  = head;
    bool t1{true},t2{true};
    bool carry = false;

    int counts{0};

    do{
        int sum{0};
        if(l1){
            sum+=l1->val;
            t1 = l1->next;
            l1 = l1->next;
        }
        if(l2){
            sum+=l2->val;
            t2 = l2->next;
            l2 = l2->next;
        }
        if(carry){ sum++;   carry = false; }
        if(sum>9){ sum-=10; carry = true ; }
        ptr->val=sum;
        if((t1||t2)||carry){
            ptr->next=new ListNode(-1);
        }
        if(ptr->next)
        ptr=ptr->next;
    }while(t1 || t2 || carry); 
    return head;
}
};

解题成功效果不是很好还可以进一步优化