Add Two Numbers II

https://leetcode.com/problems/add-two-numbers-ii/description/

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.

Thoughts

两个很大的数用linked list表示，低位在list尾，每个结点为一个数字，让返回两个数字相加后的数用list表示。t直观的想法是reverse两个原list再相加生成新的List后再翻转。生成新的list用dummy更方便。

1. 如题目不允许修改原list, 因此不能翻转。用stack依次存入再吐出做辅助翻转。

2. 相加时新node的next是上一个node. 直接返回最后一个node即可。

Code

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<ListNode*> s1, s2;
        while (l1 != NULL) {
            s1.push_back(l1);
            l1 = l1->next;
        }
        while (l2 != NULL) {
            s2.push_back(l2);
            l2 = l2->next;
        }

        int carry = 0; ListNode *p = NULL;
        while (!s1.empty() || !s2.empty() || carry != 0) {
            int a = s1.empty() ? 0 : s1[s1.size() - 1]->val;
            int b = s2.empty() ? 0 : s2[s2.size() - 1]->val;
            if (!s1.empty()) s1.pop_back();
            if (!s2.empty()) s2.pop_back();
            const auto res = a + b + carry;
            carry = res >= 10 ? 1 : 0;
            auto node = new ListNode(res % 10);
            node->next = p;
            p = node;
        }

        return p;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }

        ListNode node = null;
        int carry = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int a = stack1.isEmpty() ? 0 : stack1.pop();
            int b = stack2.isEmpty() ? 0 : stack2.pop();
            ListNode newNode = new ListNode((a + b + carry) % 10);
            newNode.next = node;
            node = newNode;
            carry = (a + b + carry) >= 10 ? 1 : 0; 
        }

        return node;
    }
}

Analysis

Errors:

1. 忘了判断最后addon是不是1，出现了5+5=0的情况。

2. 不能用转string再转int做，因为给的input位数无限制。

做题耗时16min

时间复杂度O(n), 空间复杂度O(n).