# 问题 原题链接：[https://leetcode.com/problems/add-two-numbers-ii/](https://leetcode.com/problems/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 ``` # 分析过程 - 输入：两个含单位数字的链表 - 输出：相加以后的结果链表 - 思路：其实是个大数加法。Follow up 中不允许反转链表，那么可以用栈来处理，元素全部压栈，从后面弹栈来相加。需要注意的是长度不一样的两个数，栈的深度不一样，需要特殊处理。另外最后的进位也需要单独处理。 # 解决方法 ```cpp class Solution { public: std::vector<ListNode *> stackForNum(ListNode *num) { std::vector<ListNode *> stack; ListNode *tmp = num; while (tmp) { stack.push_back(tmp); tmp = tmp->next; } return stack; } ListNode *addNode(ListNode *n1, ListNode *n2, int carry, int *carryOut) { int sum = carry; // nullptr的节点不会被相加 if (n1) { sum += n1->val; } if (n2) { sum += n2->val; } *carryOut = sum / 10; return new ListNode(sum % 10); } ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { // 使用栈反转链表 std::vector<ListNode *> numStack1 = stackForNum(l1); // 使用栈反转链表 std::vector<ListNode *> numStack2 = stackForNum(l2); // 结果栈 std::vector<ListNode *> resultStack; // 进位 int carry = 0; while (!(numStack1.empty() && numStack2.empty())) { // 节点相加，如果栈到末尾了，用 nullptr ListNode *n1 = numStack1.empty() ? nullptr : ({ ListNode *back = numStack1.back(); numStack1.pop_back(); back; }); ListNode *n2 = numStack2.empty() ? nullptr : ({ ListNode *back = numStack2.back(); numStack2.pop_back(); back; }); ListNode *r = addNode(n1, n2, carry, &carry); resultStack.push_back(r); } // 最后处理进位 if (carry) { resultStack.push_back(new ListNode(1)); } if (resultStack.empty()) { // 如果结果是空栈，返回 0 return new ListNode(0); } else { // 最后将结果栈反转得到最终链表 ListNode resultRoot = ListNode(0); ListNode *tmp = &resultRoot; while (!resultStack.empty()) { tmp->next = resultStack.back(); resultStack.pop_back(); tmp = tmp->next; } return resultRoot.next; } } }; ```