445. 两数相加 II

题目描述

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

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

示例1：
在这里插入图片描述

输入：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中的数是正序存储。两数相加的直观思维是竖式加法，而竖式加法正好满足逆序，现在既然是正序，那么就可以考虑如何将正序转换为逆序，此时正好利用栈结构的特性即可。

代码可能稍显冗余，但是思路较为清晰。