今天的題目是兩數相加。

2.Add Two Numbers

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

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

2. 兩數相加

給出兩個 非空 的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照 逆序 的方式存儲的，并且它們的每個節點只能存儲 一位 數字。

如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。

您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

示例：

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

輸出：7 -> 0 -> 8

原因：342 + 465 = 807

My answer:

首先創建兩個指針指向結果鏈表的頭節點，一個指針dummy始終指在頭節點，一個指針now用來指向尾結點(新值插入的位置)。然后設置一個進位標志carry初始化為0。x來代表l1的數值，y代表l2數值，任意一個鏈表的結束時其對應數值設為0，直到兩個鏈表均結束循環停止。然后在循環內，獲得當前位的值sum = x+y+carry和進位carry = sum//10，并將新值sum%10接在now指針后面。最后循環結束時，判斷是否依然有進位，如果有進位則在結果鏈表后新增值為1的結點即可。最后返回dummy.next(注意返回時略過頭節點)鏈表。

Runtime: 40 ms, faster than 99.89% of Python online submissions for Add Two Numbers.

     Memory Usage: 11.9 MB, less than 31.51% of Python online submissions for Add Two Numbers.

# 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
        """
        now = dummy = ListNode(0) #new node 
        carry = 0
        while(l1 or l2):
            x = l1.val if l1 is not None else 0
            y = l2.val if l2 is not None else 0
            sum = x+y+carry
            carry = sum//10
            now.next = ListNode(sum%10)
            now = now.next
            if(l1): l1 = l1.next
            if(l2): l2 = l2.next
        if(carry):
            now.next = ListNode(1)
        return dummy.next