高精度加法实现(c++)

0
11

给出两个非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储一位数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

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

示例:

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

程序代码如下:

#include <iostream>
#include <cstdio>
using namespace std;
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2);

int main()
{
    int  m,n;
    cin>>m>>n;
    int temp_m;
    cin>>temp_m;
    ListNode *head_m = new ListNode(temp_m);
    ListNode *index = head_m;
    for(int i = 0;i<m-1;++i)
    {
        cin>>temp_m;
        ListNode *new_m_node = new ListNode(temp_m);
        index->next = new_m_node;
        index = new_m_node;
    }
    int temp_n;
    cin>>temp_n;
    ListNode*head_n = new ListNode(temp_n);
    index = head_n;
    for(int i = 0;i<n-1;++i)
    {
        cin>>temp_n;
        ListNode *new_n_node = new ListNode(temp_n);
        index->next = new_n_node;
        index = new_n_node;
    }
    ListNode *ans = addTwoNumbers(head_m, head_n);
    while (ans->next!=NULL)
    {
        cout<<ans->val<<endl;
        ans = ans->next;
    }
    cout<<ans->val;
    return 0;
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
{
    bool flag = true;
    ListNode *ans = NULL;
    ListNode *ans_head = NULL;
    bool ifadd = false;
    while (l1!=NULL&&l2!=NULL)
    {
        if(!ifadd)
        {
            if(flag)
            {
                flag = false;
                ans = new ListNode((l1->val+l2->val)%10);
                ans_head = ans;
            }
            else
            {
                ans->next = new ListNode((l1->val+l2->val)%10);
                ans = ans->next;
            }
            if((l1->val+l2->val)/10==1)
                ifadd = true;
            l1 = l1->next;
            l2 = l2->next;
        }
        else
        {
            if(flag)
            {
                flag = false;
                ans = new ListNode((l1->val+l2->val+1)%10);
                ans_head = ans;
            }
            else
            {
                ans->next = new ListNode((l1->val+l2->val+1)%10);
                ans = ans->next;
            }
            if((l1->val+l2->val+1)/10==0)
                ifadd = false;
            l1 = l1->next;
            l2 = l2->next;
        }
    }
    if(l1==NULL&&l2==NULL)
    {
        if (ifadd)
        {
            ans->next = new ListNode(1);
        }
        else
        {
            return ans_head;
        }
    }
    if(l1==NULL&&l2!=NULL)
    {
        l1 = l2;
    }
    while (l1!=NULL)
    {
        if(!ifadd)
        {
            if(flag)
            {
                flag = false;
                ans = 
                ans_head = ans;
            }
            else
            {
                ans->next = new ListNode((l1->val)%10);
                ans = ans->next;
            }
            
            if((l1->val)/10==1)
                ifadd = true;
            l1 = l1->next;
        }
        else
        {
            if(flag)
            {
                flag = false;
                ans = new ListNode((l1->val+1)%10);
                ans_head = ans;
            }
            else
            {
                ans->next = new ListNode((l1->val+1)%10);
                ans = ans->next;
            }
            
            if((l1->val+1)/10==0)
                ifadd = false;
            l1 = l1->next;
        }
    }
    if (ifadd)
    {
        ans->next = new ListNode(1);
    }
    else
    {
        return ans_head;
    }
    return ans_head;
}

在该题目中,我总共犯了两个错误:

1.在对指针赋值时,将空指针赋值给要创建对象的指针,导致新实例化的对象,并没有进入到链表当中。

2.忘记处理最后的进位

如若该题目改成链表的存储方式为由高位到低位存储,则还需要再建立一个反向的单链表由低位到高位存储答案,以便于发生多次进位的时候逐级向高位进位。

<

发布回复

请输入评论!
请输入你的名字