Question 2

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

題目分析

輸入：本題的輸入是兩個(gè)自然數(shù)，每個(gè)數(shù)都逆序放在鏈表里，比如例子中的 (2 -> 4 -> 3)實(shí)際上是342。并且默認(rèn)除了0以外，自然數(shù)的不會(huì)以0作為開頭，也就是說342不會(huì)以 (2 -> 4 -> 3 - > 0)的形式存在（即0342）。
處理：函數(shù)作用是將兩個(gè)鏈表中的自然數(shù)相加，同樣除了0以外的數(shù)不以0開頭，比如例子中342+465=807。
輸出：將結(jié)果以鏈表形式輸出，即把結(jié)果807用鏈表 (7 -> 0 -> 8)輸出。

檢驗(yàn)設(shè)置

TDD(Test-driven development) analysis:

1. 最簡單的情形是兩個(gè)數(shù)位數(shù)相同且加和不進(jìn)位：
l1 =  (2 -> 4 -> 3), l2 =  (3 -> 2 -> 5)
>>>  (5 -> 6 -> 8)
2. 同樣加和不進(jìn)位的情形下，使兩個(gè)數(shù)位數(shù)不同：
l1 =  (2 -> 4 -> 3), l2 =  (2 -> 5)
>>> (4 -> 9 -> 3)
3. 位數(shù)相/不同的兩個(gè)數(shù)加和進(jìn)位，但保持結(jié)果的鏈表長度等于輸入兩個(gè)鏈表的最大長度：
l1 =  (2 -> 4 -> 3), l2 =  (3 -> 7 -> 5)
>>> (5 -> 1 -> 9)
4. 位數(shù)相/不同的兩個(gè)數(shù)加和進(jìn)位，且結(jié)果的鏈表長度大于輸入兩個(gè)鏈表的最大長度：
l1 =  (2 -> 4 -> 3), l2 =  (3 -> 7 -> 6)
>>> (5 - > 1 -> 0 -> 1)
5. 特殊情況，兩個(gè)數(shù)都是0：
l1 =  (0), l2 =  (0)
>>> (0)

鏈表的結(jié)構(gòu)要事先定義好，這里與題目給出的class一致，鏈表當(dāng)中的值用val表示，連接用next表示，如下

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

為了方便檢驗(yàn)，還需要寫兩個(gè)函數(shù)分別實(shí)現(xiàn)創(chuàng)建鏈表和顯示鏈表的功能。

#根據(jù)輸入的列表創(chuàng)建鏈表，列表與鏈表的順序一致
#l = [2, 4, 3]（代表自然數(shù)342）
#>>> (2 - > 4 - > 3)
def createListNode(l):
    head = temp = ListNode(0)
    #先設(shè)置一個(gè)head，像基因編碼一樣找一個(gè)生成器
    for i in l:
        temp.next = ListNode(i)
        #將輸入list中的每個(gè)元素變成一個(gè)鏈表結(jié)構(gòu)
        temp = temp.next
    return head.next
    #返回需要的鏈表，扔掉編碼開始的head

#顯示鏈表
#l = (2 - > 4 - > 3)
#>>> 243
def printListNode(ln):
    while ln:
        print(ln.val, end = '')
        #按照鏈表順序輸出value，同時(shí)不換行
        ln = ln.next
    print('')
    #換行，使得后續(xù)輸出的結(jié)果在新一行出現(xiàn)，容易辨認(rèn)

1.直接解法（Python3）:

既然是在自然數(shù)加法上復(fù)合了鏈表，直接的解法是單獨(dú)處理鏈表與加和：先把輸入的鏈表轉(zhuǎn)換為自然數(shù)，再把加和后的結(jié)果轉(zhuǎn)換為鏈表。

def addTwoNumbers(l1, l2):
    def lnToInt(ln):
    #將鏈表（縮寫為名稱的ln，listnode）轉(zhuǎn)化為整型數(shù)（縮寫為名稱的int）
        num = count = 0
        #num代表轉(zhuǎn)化后的整型數(shù)，count代表數(shù)位
        while ln:
            num += ln.val * pow(10, count)
            #把鏈表每個(gè)數(shù)字放到整型數(shù)對應(yīng)的位數(shù)上，所以乘以了10的count次方
            count += 1
            ln = ln.next
        return num

    def intToLn(n):
    #將整型數(shù)轉(zhuǎn)換為鏈表
        head = temp = ListNode(0)
        #先設(shè)置一個(gè)head，像基因編碼一樣找一個(gè)生成器
        if n == 0:
            return head
        #如果整型數(shù)為0，直接返回鏈表(0)，這也是head設(shè)置為ListNode(0)的好處
        while n:
            temp.next = ListNode(n % 10)
            #找到余數(shù)，也就是鏈表對應(yīng)的1位數(shù)元素
            temp = temp.next
            n = n // 10
            #獲得剩下未轉(zhuǎn)換為鏈表的整型數(shù)
        return head.next
    sum = lnToInt(l1) + lnToInt(l2)
    return intToLn(sum)

時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)，鏈表與加和分開處理的思考難度低，但是效率被浪費(fèi)在鏈表和自然數(shù)的相互轉(zhuǎn)化中，可以繼續(xù)優(yōu)化，方向是賦予鏈表加和能力。

2.鏈表的加法運(yùn)算：

實(shí)現(xiàn)鏈表加法的核心有兩個(gè)：進(jìn)位問題和鏈表長度變化問題。這兩個(gè)問題都是由鏈表表示自然數(shù)的規(guī)定引發(fā)的，規(guī)定中要求每一個(gè)鏈表元素都只能是1位數(shù)，如果加和出現(xiàn)兩位數(shù)是在鏈表中間，就是進(jìn)位問題，在鏈表末端就是長度變化問題。解決方案是用一個(gè)變量來記錄進(jìn)位的數(shù)字，比如用carry來記錄，鏈表的元素取加和后結(jié)果的個(gè)位數(shù)，比如，5+7=12，這時(shí)鏈表的元素取個(gè)位數(shù)2，carry=1，當(dāng)下一位進(jìn)行計(jì)算的時(shí)候把carry的值加入。

def addTwoNumbersNode(l1, l2):
    head = temp = ListNode(0)
    #先設(shè)置一個(gè)head，像基因編碼一樣找一個(gè)生成器
    carry = 0
    #用來存放加和是兩位數(shù)時(shí)的十位數(shù)
    while l1 or l2 or carry:
    #只有當(dāng)l1和l2是null，且carry是0的時(shí)候才停止生成鏈表
        value1 = l1.val if l1 else 0
        value2 = l2.val if l2 else 0
        sum = value1 + value2 + carry
        temp.next = ListNode(sum % 10)
        #鏈表的元素是加和值的個(gè)位數(shù)
        carry = sum // 10
        #carry的值是加和值的十位數(shù)
        temp = temp.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    return head.next

時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)，實(shí)現(xiàn)了鏈表和加法的功能組合。