两数相加 II

问题描述

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers-ii

思路

数字相加的时候是从链表的末端开始的，所以用栈将两个链表存储起来会比较合适。
和两数相加I的思路一样，将情况分为3种：
1、两个栈都不为空
2、栈1为空
3、栈2为空
将每次相加的结果取余，余数为低位，压入栈中，栈底就是sum的最低位。
进位为相加的结果/10。
需要注意的是进位也要参与每次的加法。

通过栈构建链表时，需要特别注意：

ListNode *ret 为要返回的头节点。
一定要先建立cur = new ListNode(tmp.top());再让 ret = cur;
否则，ret只有一个节点。

题解

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        stack<int> stack1;
        stack<int> stack2;
        stack<int> tmp;
        int addtion = 0;
        while (l1 != nullptr) {
            stack1.push(l1->val);
            l1 = l1->next;
        }
        while (l2 != nullptr) {
            stack2.push(l2->val);
            l2 = l2->next;
        }
        while (!stack1.empty() || !stack2.empty()) {
            if (!stack1.empty() && !stack2.empty()) {
                tmp.push((stack1.top() + stack2.top() + addtion) % 10);
                addtion = (stack1.top() + stack2.top() + addtion) / 10;
                stack1.pop();
                stack2.pop();
            } else if (!stack1.empty()) {
                tmp.push((stack1.top() + addtion) % 10);
                addtion = (stack1.top() + addtion) / 10;
                stack1.pop();
            } else {
                tmp.push((stack2.top() + addtion) % 10);
                addtion = (stack2.top() + addtion) / 10;
                stack2.pop();
            }
        }
        ListNode *ret, *cur = nullptr;

        if (addtion == 1) {
            tmp.push(1);
        }
        while (!tmp.empty()) {
            if (cur == nullptr) {
                cur = new ListNode(tmp.top());
                ret = cur;
                tmp.pop();
            } else {
                cur->next = new ListNode(tmp.top());
                tmp.pop();
                cur = cur->next;
            }
        }
        return ret;
    }
};