题目：
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
解法：
方法一：先逆转，再相加；
方法二：
本题的主要难点在于链表中数位的顺序与我们做加法的顺序是相反的，为了逆序处理所有数位，我们可以使用栈：把所有数字压入栈中，再依次取出相加。计算过程中需要注意进位的情况。
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* addTwoNumbers1(ListNode* l1, ListNode* l2) 12 { 13 stack<int> s1; 14 stack<int> s2; 15 16 while (l1) 17 { 18 s1.push(l1->val); 19 l1 = l1->next; 20 } 21 22 while (l2) 23 { 24 s2.push(l2->val); 25 l2 = l2->next; 26 } 27 28 int carry = 0; 29 ListNode *pre = new ListNode(0); 30 ListNode *cur = pre; 31 while (!s1.empty() || !s2.empty()) 32 { 33 int x = s1.empty() ? 0 : s1.top(); 34 int y = s2.empty() ? 0 : s2.top(); 35 int sum = x + y + carry; 36 carry = sum / 10; 37 sum = sum % 10; 38 cur->next = new ListNode(sum); 39 40 cur = cur->next; 41 42 if (!s1.empty()) 43 { 44 s1.top(); 45 } 46 if (!s2.empty()) 47 { 48 s2.top(); 49 } 50 } 51 52 if (carry == 1) 53 { 54 cur->next = new ListNode(carry); 55 } 56 57 return pre->next; 58 } 59 60 // 61 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { 62 stack<int> s1, s2; 63 while (l1) { 64 s1.push(l1 -> val); 65 l1 = l1 -> next; 66 } 67 while (l2) { 68 s2.push(l2 -> val); 69 l2 = l2 -> next; 70 } 71 int carry = 0; 72 ListNode* ans = nullptr; 73 while (!s1.empty() or !s2.empty() or carry != 0) { 74 int a = s1.empty() ? 0 : s1.top(); 75 int b = s2.empty() ? 0 : s2.top(); 76 if (!s1.empty()) s1.pop(); 77 if (!s2.empty()) s2.pop(); 78 int cur = a + b + carry; 79 carry = cur / 10; 80 cur %= 10; 81 auto curnode = new ListNode(cur); 82 curnode -> next = ans; 83 ans = curnode; 84 } 85 return ans; 86 } 87 };
原文：https://www.cnblogs.com/ocpc/p/12814866.html