###### tags: `LeetCode` `Linked List` `Medium` `Stack`
# LeetCode #445 [Add Two Numbers II](https://leetcode.com/problems/add-two-numbers-ii/)
### (Medium)

給你兩個 非空 鏈結串列來代表兩個非負整數。數字最高位位於鏈結串列開始位置。它們的每個節點只存儲一位數字。將這兩數相加會返回一個新的鏈結串列。

你可以假設除了數字 0 之外，這兩個數字都不會以零開頭。

---
使用vector:將兩個ListNode的值分別存入vector中, 然後將數組反轉, 之後讀取兩數組中的元素並相加, 若數組元素不存在(一開始的兩個ListNode長度不見得一樣)則為0, 並將和存入另一個數組中。

完成後再將數組反轉, 並從頭開始建立回傳用的ListNode。

記得進位。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<int> v1, v2;
        while(l1){
            v1.push_back(l1->val);
            l1=l1->next;
        }
        while(l2){
            v2.push_back(l2->val);
            l2=l2->next;
        }
        reverse(v1.begin(), v1.end());
        reverse(v2.begin(), v2.end());
        int c = 0;
        int i1=v1.size(), i2=v2.size();
        vector<int> v3(max(i1,i2));
        for(int i=0;i<v3.size();i++){
            int n = (i>=i1?0:v1[i]) + (i>=i2?0:v2[i]) + c;
            c = n>=10;
            v3[i]= n%10;
        }
        if(c==1)v3.push_back(1);
        reverse(v3.begin(), v3.end());
        ListNode *ans = nullptr, *tmp = nullptr, *prev = nullptr; 
        for(int i =0;i<v3.size();i++){
            tmp = new ListNode(v3[i]);
            if(!prev)ans = tmp;
            else prev->next = tmp;
            prev = tmp;
        }
        return ans;
    }
};

---
使用stack:利用堆疊先進後出的概念, 可以免去上面vector版的反轉, 除此之外並無不同, 執行速度比vector版快一點。

記得進位。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
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 = nullptr, *prev = nullptr, *tmp = nullptr;
        int c = 0;
        stack<int> s3;
        while(!s1.empty()||!s2.empty()){
            int n1 = 0, n2 = 0;
            if(!s1.empty()){
                n1 = s1.top();s1.pop();
            }
            if(!s2.empty()){
                n2 = s2.top();s2.pop();
            }
            int n = ((n1+n2+c)%10);
            s3.push(n);
            c = (n1+n2+c)>=10;
        }
        if(c==1){
            s3.push(1);
        }
        
        while(!s3.empty()){
            tmp = new ListNode(s3.top());s3.pop();
            if(!prev)ans = tmp;
            else prev->next = tmp;
            prev = tmp;
        }
        
        return ans;
    }
};