难度中等140
给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912**进阶：**思考一下，假设这些数位是正向存放的，又该如何解决呢?
示例：
输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912思路：
这道题与数组求和以及字符串求和类似，都是用每一位相加还有加上进位求得结果赋给一个新的链表 tmp，直到两个链表都遍历完。但记得最后判断是否还有多的一个进位需要加上。
题目中还提到如果是正向存放的话，那可以先用将两个链表的值放到两个栈中，然后就像原来是思路一样，只不过变成了从栈中取数值而已！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//创建一个头节点
ListNode* newhead = new ListNode(-1);
//创建一个新链表用于存储每个位的和
ListNode* tmp = new ListNode(0);
newhead->next = tmp;
int next = 0; //表示进位
while(l1 != nullptr || l2 != nullptr)
{
int n1 = 0;
if(l1 != nullptr)
{
n1 = l1->val;
l1 = l1->next;
}
int n2 = 0;
if(l2 != nullptr)
{
n2 = l2->val;
l2 = l2->next;
}
int sum = n1 + n2 + next;
if(sum > 9) //判断是否需要进位
{
sum -= 10;
next = 1;
}
else
{
next = 0;
}
tmp->val = sum;
if(l1 != nullptr || l2 != nullptr)
{
ListNode* tmp1 = new ListNode(0);
tmp->next = tmp1;
tmp = tmp1;
}
}
if(next == 1)
{
ListNode* tmp1 = new ListNode(0);
tmp->next = tmp1;
tmp1->val = 1;
}
//将头节点释放
ListNode* t = newhead->next;
delete newhead;
return t;
}
};