[Leetcode]2:Add Two Numbers

Link : https://leetcode.com/problems/add-two-numbers/

Problem :
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, 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.

把兩個linklist裡面的node值相加的題目，加法的進位方式跟一般我們常用的不太一樣。舉例來說(參考下面的圖)

Example 1 :
2 -> 4 ->3
5-> 6 -> 4
7 ->10 ->7 (進位以後 : 7 ->0(留個位數就好，十位數1進位到右邊) -> 8(7+1))

Example 3 :
9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9
9 -> 9 -> 9 -> 9
18 -> 18 -> 18 ->18 -> 9 -> 9 -> 9
進位步驟：
8 ->19 -> 18 -> 18 -> 9 -> 9 -> 9
8 -> 9 -> 19 -> 18 -> 9 -> 9 -> 9
8 -> 9 -> 9 -> 19 -> 9 -> 9 -> 9
8 -> 9 -> 9 -> 9 -> 10 -> 9 -> 9
8 -> 9 -> 9 -> 9 -> 0 -> 10 -> 9
8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 10
8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1

圖來自leetcode

Thoughts :
1. new一個新的 linklist來存加完的result。
2. 把 l1 的第一個 node 跟 l2 的 第一個 node 加起來。
3. 檢查個位數跟十位數，個位數存起來，十位數往後一位存。

Solution :

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        result = ListNode(0)
        node = result
        tmp = 0
        while l1 is not None or l2 is not None or tmp>0:
            if l1 is not None:
                tmp = tmp + l1.val
                l1 = l1.next
            if l2 is not None:
                tmp = tmp + l2.val
                l2 = l2.next
            node.next = ListNode(tmp%10) #餘數
            node = node.next
            tmp = tmp//10 #商數
        return result.next

time complexity = O(n)?, space complexity = O(1)?