【每日一题】445. 两数相加 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题】445. 两数相加 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

445. 两数相加 II

题目描述

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例1：
【每日一题】445. 两数相加 II,每日一题,面试,算法,职场和发展

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

输入：l1 = [0], l2 = [0]
输出：[0]

提示：

链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0

进阶：如果输入链表不能翻转该如何解决？

解题思路

思路：栈+竖式加法。分别使用栈st1、st2存储链表1、2元素，使用sum表示当前和，使用add表示进位，使用cur表示当前位。首先是两个指针均不为空时的处理，接着是两个指针两者之一为空时的处理，最后要注意残留add时的处理。

/**
 * 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) {
        //既然链表正序存储 那么就使用栈来存储 利用栈先进后出的性质
        stack<int> st1,st2;
        while(l1)
        {
            st1.push(l1->val);
            l1=l1->next;
        }
        while(l2)
        {
            st2.push(l2->val);
            l2=l2->next;
        }
        //剩下的本质上和2一样
        int sum;
        int cur;
        int add=0;
        ListNode* L=new ListNode();
        while(!st1.empty()&&!st2.empty())
        {
            sum=(st1.top()+st2.top()+add);
            cur=sum%10;
            add=sum/10;
            ListNode* temp=new ListNode(cur);
            temp->next=L->next;
            L->next=temp;
            st1.pop();
            st2.pop();
        }
        while(!st1.empty())
        {
            sum=(st1.top()+add);
            cur=sum%10;
            add=sum/10;
            ListNode* temp=new ListNode(cur);
            temp->next=L->next;
            L->next=temp;
            st1.pop();
        }
        while(!st2.empty())
        {
            sum=(st2.top()+add);
            cur=sum%10;
            add=sum/10;
            ListNode* temp=new ListNode(cur);
            temp->next=L->next;
            L->next=temp;
            st2.pop();
        }
        if(add)
        {
            ListNode* temp=new ListNode(add);
            temp->next=L->next;
            L->next=temp;
        }
        return L->next;
    }
};

总结：两数相加II和两数相加的唯一区别在于，两数相加中的数是逆序存储，而两数相加II中的数是正序存储。两数相加的直观思维是竖式加法，而竖式加法正好满足逆序，现在既然是正序，那么就可以考虑如何将正序转换为逆序，此时正好利用栈结构的特性即可。

代码可能稍显冗余，但是思路较为清晰。文章来源地址https://www.toymoban.com/news/detail-516548.html

到了这里，关于【每日一题】445. 两数相加 II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！