# Add Two Numbers
###### tags: `Medium`


*********** 注意 ************
1.就只是用一個新的linked list來儲存相加後的結果
2.要注意的就是list1跟list2長度可能不一樣
3.另外就是相加後可能比9還大，需要考慮進位的情況

def lst2link(lst):
    cur = dummy = ListNode(0)
    for e in lst:
        cur.next = ListNode(e)
        cur = cur.next
    return dummy.next
            
class Solution(object):
    
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        #### reverse
        len1 = 0
        len2 = 0
        list1 = []
        list2 = []
        key = 0
        key2 = 0
        if l1.next == None:
            s1 = l1.val
            key = 1
        if l2.next == None:
            s2 = l2.val  
            key2 = 1
        
        if key == 0:
            s1 = ""
            while l1.val != None:
                print(l1.val)
                list1.append(l1.val)
                l1 = l1.next
                len1 += 1
                if l1.next == None:
                    print(l1.val)
                    list1.append(l1.val)
                    len1 += 1
                    break
            for l in range(len1):
                s1 += str(list1[l])
            s1 = s1[::-1]    
            s1 = int(s1)
        if key2 == 0:    
            s2 = ""
            while l2.val != None:
                print(l2.val)
                list2.append(l2.val)
                l2 = l2.next
                len2 += 1
                if l2.next == None:
                    print(l2.val)
                    list2.append(l2.val)
                    len2 += 1
                    break
            for l in range(len2):
                s2 += str(list2[l])
            s2 = s2[::-1]
            s2 = int(s2)
        print(s1)
        print(s2)
     
        ### sum 
        s = s1 + s2
        print('sum = ',s)
        
        #### reverse(output)
        out = []
        s = str(s)[::-1]
        for l in range(len(s)):
        #    output.val = s[l]
            out.append(int(s[l]))
        output = lst2link(out)            
        return output

- 想法:

-大神寫法:

    def addTwoNumbers(self, l1, l2, ten = 0):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 == None and l2==None and ten == 0:
            return None 
        if l1 == None and l2==None and ten!=0:
            return ListNode(1)
        if l1 == None:
            l1 = ListNode()
        if l2 == None:
            l2 = ListNode()
        sum_current = l1.val + l2.val
        digit = sum_current % 10 + ten
        if digit == 10:
            digit = 0
            ten = 1
        else: ten = sum_current // 10
        L = ListNode(digit,self.addTwoNumbers(l1.next, l2.next,ten))
        return L

/**
 * 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) {
        int sum = 0;
        
        //新創一個linked list存相加結果       
        ListNode *l3 = NULL;
        ListNode **node = &l3;
        
        while(l1!=NULL || l2!=NULL || sum>0)
        {
          //每個linked list長度可能不同->分開處理
            if(l1 != NULL) {
                sum += l1->val;
                l1=l1->next;
            }
            
            if(l2 != NULL) {
                sum += l2->val;
                l2=l2->next;
            }
            
   //個位數存進l3 十位數留到下一個節點相加          
            (*node) = new ListNode(sum%10);
            sum = sum/10;
            node = &((*node)->next);
        }
        
        return l3;
    }
};