【python3】leetcode 445. Add Two Numbers II (Medium)

 445. 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 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.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7      

1 題目要求不reverse ，是以轉換成str求和，然後再轉回ListNode  time O(n),space O(n)

在discussion裡看到一個回複說的隐患 ：You cannot do this way, because, integer overflow occurs, if linked list is big enough. The main objective of linked list addition is to use for big integers.如果兩個連結清單長一點，轉成int就會超出int的範圍。我覺得說的很有道理，是以雖然這種解法Accepted但是還不不太可取。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        a = '';b = ''
        while(l1):
            a += str(l1.val)
            l1 = l1.next
        while(l2):
            b += str(l2.val)
            l2 = l2.next
        c = str(int(a) + int(b))
        l3 = ListNode(int(c[0]))
        node = l3
        for i in range(1,len(c)):
            node.next = ListNode(int(c[i]))
            node = node.next
        return l3
           

2 雖然不能轉成int 但還是可以先把val提出到容器中（如str或list）然後按位相加

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        a = [];b = []
        while(l1):
            a.append(l1.val)
            l1 = l1.next
        while(l2):
            b.append(l2.val)
            l2 = l2.next
        tag = 0
        c = []
        maxlen = max(len(a),len(b))
        #對齊補0
        if len(a) < maxlen:
            for i in range(maxlen - len(a)):a.insert(0,0)
        if len(b) < maxlen:
            for i in range(maxlen - len(b)):b.insert(0,0)        
        
        for i in range(0,maxlen):
            sum = a[maxlen-i-1] + b[maxlen-i-1] + tag
            tag = 1 if sum >= 10 else 0
            c.insert(0,str(sum%10))
        if tag == 1:
            c.insert(0,1)
        l3 = ListNode(c[0])
        node = l3
        for i in range(1,len(c)):
            node.next = ListNode(int(c[i]))
            node = node.next
        node.next = None
        return l3