今天的題目是兩數(shù)相加。

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. 兩數(shù)相加

給出兩個(gè) 非空 的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。

如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。

您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭。

示例：

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

輸出：7 -> 0 -> 8

原因：342 + 465 = 807

My answer:

首先創(chuàng)建兩個(gè)指針指向結(jié)果鏈表的頭節(jié)點(diǎn)，一個(gè)指針dummy始終指在頭節(jié)點(diǎn)，一個(gè)指針now用來(lái)指向尾結(jié)點(diǎn)(新值插入的位置)。然后設(shè)置一個(gè)進(jìn)位標(biāo)志carry初始化為0。x來(lái)代表l1的數(shù)值，y代表l2數(shù)值，任意一個(gè)鏈表的結(jié)束時(shí)其對(duì)應(yīng)數(shù)值設(shè)為0，直到兩個(gè)鏈表均結(jié)束循環(huán)停止。然后在循環(huán)內(nèi)，獲得當(dāng)前位的值sum = x+y+carry和進(jìn)位carry = sum//10，并將新值sum%10接在now指針后面。最后循環(huán)結(jié)束時(shí)，判斷是否依然有進(jìn)位，如果有進(jìn)位則在結(jié)果鏈表后新增值為1的結(jié)點(diǎn)即可。最后返回dummy.next(注意返回時(shí)略過(guò)頭節(jié)點(diǎn))鏈表。

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