LeetCode Add Two Numbers II You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed. Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7
有两个数字链表，分别存储了两个整数，要求把这两个整数加起来。和LeetCode Add Two Numbers的区别是，之前的链表最低位在表头，我们正常加法也是从低位到高位，所以之前的题可以直接从表头开始加。但是这个题稍有不同，最低位在表尾，表头是最高位，所以必须先跑到链表尾才能做加法。一种方法是我们可以先把链表逆序，这样就可以用之前的解法了，但是题目中说不能修改原链表，所以不能用这种解法。 那么怎样获取到表尾的数据进行加法呢，我们可以把两个链表压入两个堆栈，因为堆栈是后进先出，所以再次从栈顶取数据做加法的时候就是从低位到高位的加了。 完整代码如下： [cpp] class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { stack<int> s1, s2; while (l1) { s1.push(l1->val); l1 = l1->next; } while (l2) { s2.push(l2->val); l2 = l2->next; } ListNode* ans = new ListNode(1); // 预设好的最高位进位:-) int sum = 0; while (!s1.empty() || !s2.empty()) { if (!s1.empty()) { sum += s1.top(); s1.pop(); } if (!s2.empty()) { sum += s2.top(); s2.pop(); } ListNode* tmp = new ListNode(sum%10); tmp->next = ans->next; ans->next = tmp; sum /= 10; // 下一次的进位 } if (sum)return ans; else return ans->next; } }; [/cpp] 本代码提交AC，用时55MS。 代码中有两个地方解释一下，一般链表的题都会在结果链表中加一个没用的头结点，一般是0，但是因为最终的加法结果可能进位，所以把表头的值定为1，如果有进位，这个1也可以用上，如果没进位，就返回1的next。另一个就是我们没有单独定义add1、add2和carry，而是只用一个sum变量搞定了，sum%10相当于进位之后的结果，sum/10相当于进位。]]>