[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)?