###### tags: `Leetcode` `medium` `list` `stack` `python` `c++`

# 445. 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 contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

**Follow up**: Could you solve it without reversing the input lists?


## 解題想法:
* 此題為求兩list位元相加，最高位元在list head，不能反轉的情況下，使用O(N)time

* 想法: 使用Stack
* Step1: 先用兩個stack(list1, list2)分別存l1、l2的所有元素
* Step2: 額外需要兩變數
* dummy老朋友，作為判斷最終解位置
* carry=0 ，用以判斷相加和是否溢位
* Step3: **while list1 or list2 or carry**
* 1. 每次pop出list1、list2頂端元素(若為list空則為0)
* val1= list1.pop() if list1 else 0
* val2= list2.pop() if list2 else 0
* 2. 最低位開始相加
* num=val1+val2+carry
* 3. 使用**餘數**建立node
* curNode=ListNode(num%10)
* 4. 再處理溢位
* carry=num/10
* 5. 最後再處理連接問題
* 先將當前新創的curNode連向**dummy.next**，指向最尾
* 再將dummy.next指向curNode，讓dummy保持在頭
* Step4:
* return dummy.next

## Python:

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head=self
        stack=[]
        while head:
            stack.append(head.val)
            head=head.next
        print(stack)
        
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        #stack
        list1=[]
        list2=[]
        while l1:
            list1.append(l1.val)
            l1=l1.next
        while l2:
            list2.append(l2.val)
            l2=l2.next
        #合併
        dummy=ListNode()
        carry=0 #判斷是否溢位
        while list1 or list2 or carry:
            #最低位開始加
            val1= list1.pop() if list1 else 0
            val2= list2.pop() if list2 else 0
            num=val1+val2+carry
            curNode=ListNode(num%10) #餘數建立node
            carry=num/10 #處理溢位
            #連接
            curNode.next=dummy.next #最尾巴指向None
            dummy.next=curNode #連到當前的cur_node 讓dummy保持在頭
        return dummy.next
      
    
l1=ListNode(7)
l1.insert(2)
l1.insert(4)
l1.insert(3)
l2=ListNode(5)
l2.insert(6)
l2.insert(4)
l1.printList()
l2.printList()
result = Solution()
ans=result.addTwoNumbers(l1,l2)
print('Sum of two list:',end='')
ans.printList()

## C++:

/**
 * 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> list1, list2;
        while (l1){
            list1.push(l1->val);
            l1=l1->next;
        }
        while (l2){
            list2.push(l2->val);
            l2=l2->next;
        }
        ListNode *dummy= new ListNode(0);
        int carry=0;
        while (!list1.empty() || !list2.empty() || carry){
            int val1=0, val2=0;
            if (!list1.empty()){
                val1=list1.top();
                list1.pop();
            }
            if (!list2.empty()){
                val2=list2.top();
                list2.pop();
            }
            int num=val1+val2+carry;
            //create the new node
            ListNode *curNode = new ListNode(num%10);
            carry=num/10;
            //connect
            curNode->next=dummy->next;
            dummy->next=curNode;
        }
        return dummy->next;
    }
};