题目

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶:

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例:

输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

解析

这道题和Leetcode的第2题类似
由于链表的顺序反过来了，因此是没有办法一遍完成计算的，我们可以用两个栈先把数字都收集起来，再利用后进先出的特性进行计算
向新链表插入结果的时候也要注意用头插法

代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  12.         stack<int> s1, s2;
  13.         while (l1) {
  14.             s1.push(l1->val);
  15.             l1 = l1->next;
  16.         }
  17.         while (l2) {
  18.             s2.push(l2->val);
  19.             l2 = l2->next;
  20.         }
  22.         ListNode* dummy = new ListNode(-1);
  23.         // ListNode* h = dummy;
  24.         int carry = 0, x, y;
  25.         while (!s1.empty() || !s2.empty()) {
  26.             if (s1.empty()) x = 0;
  27.             else {
  28.                 x = s1.top();
  29.                 s1.pop();
  30.             }
  31.             if (s2.empty()) y = 0;
  32.             else {
  33.                 y = s2.top();
  34.                 s2.pop();
  35.             }
  36.             int val = x + y + carry;
  37.             ListNode* p = new ListNode(val % 10);
  38.             p->next = dummy->next;
  39.             dummy->next = p;
  40.             carry = val / 10;
  41.         }
  42.         if (carry) {
  43.             ListNode* p = new ListNode(1);
  44.             p->next = dummy->next;
  45.             dummy->next = p;
  46.         }
  47.         return dummy->next;
  48.     }
  49. };