leetcode_数据结构_链表_445两数相加二(STL库stack栈的使用)

题目链接：

https://leetcode-cn.com/problems/add-two-numbers-ii/

意思就是两个数字相加，但是这两个数字分别存在两个链表中，每个链表中的一个结点代表该数字的一位。

解法：利用栈，先将两个链表中的数字反向存入两个栈中，这样栈顶即为每个数字的末位（最低位），然后就可以从两个栈的栈顶开始，分别相加，相加超过10就进位1，算到下一位相加中。

创立哑结点作为新结点的头节点，每一次栈顶两位相加后就创建一个新节点，然后用头插法插入链表中。

然后再讨论一个栈空后的情况，其实就是将另一个栈栈顶一直看为0.

这里要列以下STL stack的使用方法：

使用前添加头文件：

#include

定义：

stack a;

其中，<>中也可为其他类型。

方法：

a.push();
s.pop();
a.size();
a.top();
a.empty();

最后，附上该题代码：

/**
* 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) {}
* };
*/
#include
#include
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack a,b;
ListNode *p1=l1,*p2=l2;
ListNode *dummy=new ListNode(0);
dummy->next=nullptr;
int tag=0;//进位标志
while(p1){
a.push(p1->val);
p1=p1->next;
}
while(p2){
b.push(p2->val);
p2=p2->next;
}
while(!a.empty()||!b.empty()){
ListNode *q=new ListNode(0);
q->val=0;
if(!a.empty()&&!b.empty()){
if(tag==1)q->val=1;
tag=0;
if((a.top()+b.top()+q->val)>=10){
tag=1;
}
q->val=(a.top()+b.top()+q->val)%10;
a.pop();
b.pop();
}
else if(!a.empty()){
if(tag==1)q->val=1;
tag=0;
if(q->val+a.top()>=10){
tag=1;
}
q->val=(a.top()+q->val)%10;
a.pop();
}
else{
if(tag==1)q->val=1;
tag=0;
if(q->val+b.top()>=10){
tag=1;
}
q->val=(b.top()+q->val)%10;
b.pop();
}
q->next=dummy->next;
dummy->next=q;
}
if(tag==1){//防止5+5的情况只输出0
ListNode *q=new ListNode(0);
q->val=1;
q->next=dummy->next;
dummy->next=q;
}
ListNode *ans=dummy->next;
delete dummy;
return ans;
}
};