题目链接：
https://leetcode-cn.com/problems/add-two-numbers-ii/
意思就是两个数字相加，但是这两个数字分别存在两个链表中，每个链表中的一个结点代表该数字的一位。
解法：利用栈，先将两个链表中的数字反向存入两个栈中，这样栈顶即为每个数字的末位（最低位），然后就可以从两个栈的栈顶开始，分别相加，相加超过10就进位1，算到下一位相加中。
创立哑结点作为新结点的头节点，每一次栈顶两位相加后就创建一个新节点，然后用头插法插入链表中。
然后再讨论一个栈空后的情况，其实就是将另一个栈栈顶一直看为0.
这里要列以下STL stack的使用方法：
使用前添加头文件：
#include <stack>
定义：
stack<int> 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 <stack> #include <vector> class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { stack<int> 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; } };
leetcode_数据结构_链表_445两数相加二(STL库stack栈的使用)
原文：https://www.cnblogs.com/San-Francisco/p/14901021.html