445. Add Two Numbers II

翻转链表 O(m+n) time O(1) space

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        int c = 0;
        ListNode *res = nullptr;
        while (l1 || l2 || c > 0) {
            int a = l1 ? l1->val : 0;
            int b = l2 ? l2->val : 0;
            l1 = l1 ? l1->next : l1;
            l2 = l2 ? l2->next : l2;
            int s = a + b + c;
            auto x = new ListNode(s % 10);
            x->next = res;
            res = x;
            c = s / 10;
        }
        return res;
    }

    ListNode *reverse(ListNode *l) {
        if (!l) return l;
        ListNode *p = nullptr, *c = l;
        while (c) {
            auto s = c->next;
            c->next = p;
            p = c;
            c = s;
        }
        return p;
    }
};

两个栈 O(m+n) time O(m+n) space

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2; // 两个栈逆序放入两个链表里的数
        for (auto node = l1; node; node = node->next) {
            s1.push(node->val);
        }
        for (auto node = l2; node; node = node->next) {
            s2.push(node->val);
        }
        int a = 0, b = 0, c = 0; // 统一处理 加数 被加数 进位
        ListNode *l = nullptr;
        while (!s1.empty() || !s2.empty() || c > 0) { // 不要忘记最后进位有可能不为0！！！
            a = s1.empty() ? 0 : s1.top();
            b = s2.empty() ? 0 : s2.top();
            if (!s1.empty()) s1.pop();
            if (!s2.empty()) s2.pop();
            int s = a + b + c;
            auto n = new ListNode(s % 10);
            n->next = l;
            l = n;
            c = s / 10;
        }
        return l;
    }
};