2. Add Two Numbers

本題是 Leetcode Top 100 liked questions 中的第二題。

2. Add Two Numbers

Medium

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.

題意

題意很好理解，給你兩個鏈表，鏈表中的每個數從右到左組合起來成為一個正整數。請你將兩個鏈表所表示的值給加起來，再以相同的方式返回一個這樣的鏈表

分析

甫視此題，便想到先把鏈表的上的數都給取下來，然後再相加就得了，沒什麼新奇的。從鏈表中取數的方法也很簡單，一次從左到右去取，如果右邊有數便把它乘以相應的位數後後相加即可。得到結果後生成鏈表，只要將結果每次除10取余和商，再將商依次這麼做下去，直到商為0即可。或者直接用列表的reverse更為便捷的將它轉換即可。

Python 實現

# Definition for singly-linked list.# class ListNode(object):# def __init__(self, x):# self.val = x# self.next = None#這裡採用列表的reverse方法class Solution(object): def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ #分別去取兩個鏈表裡的數 mul=1 r1,r2=0,0 while l1: r1+=l1.val*mul l1=l1.next mul*=10 mul=1 while l2: r2+=l2.val*mul l2=l2.next mul*=10 #加和後轉換成字元串，轉置後再把每個元素還原成int r=list(map(int,str(r1+r2)))[::-1] #生成結果的鏈表，將列表的第一個值賦值給鏈表 res=ListNode(r[0]) #因為要返回鏈表的頭部，所以我們定義一個temp變數去用來循環生成鏈表 temp=res for i in r[1::]: te=ListNode(i) temp.next=te temp=te return res#數學演算法，來自@tusizi，這個代碼就很好看了。他利用carry去記錄進位，然後直接生成鏈表。不用再去reverse什麼的啦。class Solution:# @return a ListNodedef addTwoNumbers(self, l1, l2): carry = 0 root = n = ListNode(0) while l1 or l2 or carry: v1 = v2 = 0 if l1: v1 = l1.val l1 = l1.next if l2: v2 = l2.val l2 = l2.next carry, val = divmod(v1+v2+carry, 10) n.next = ListNode(val) n = n.next return root.next

Python Tips

這裡用的Python技巧不多，唯一亮點也就是那個列表生成器與map方法了。 這裡大概講一下map。引用一下python手冊里對map的定義：

map(function, iterable, ...) Apply function to every item of iterable and return a list of the results. If additional iterable arguments are passed, function must take that many arguments and is applied to the items from all iterables in parallel. If one iterable is shorter than another it is assumed to be extended with None items. If function is None, the identity function is assumed; if there are multiple arguments, map() returns a list consisting of tuples containing the corresponding items from all iterables (a kind of transpose operation). The iterable arguments may be a sequence or any iterable object; the result is always a list.

map(function,iterable,...)

讓我們舉個栗子：

>>> def f1(x):... return x*x...>>> l1=[1,2,3,4]>>> map(f1,l1)[1, 4, 9, 16]>>> l1[1, 2, 3, 4]>>>

我們可以看到對於列表l1中的每個值，都應用了f1這個函數，並將結果以一個新的列表返回了，l1的值並沒有改變。

此外，map函數可以接受多個並行參數，但前提是函數必須有能力接受這些參數。然我們再舉個栗子：

>>> l2=[4,3,2,1]>>> map(f1,l1,l2)Traceback (most recent call last):File "<stdin>", line 1, in <module>TypeError: f1() takes exactly 1 argument (2 given)>>> def f2(x,y):... return x*y...>>> map(f2,l1,l2)[4, 6, 6, 4]>>>>>> map(f2,l1,l2[1:])Traceback (most recent call last):File "<stdin>", line 1, in <module>File "<stdin>", line 2, in f2TypeError: unsupported operand type(s) for *: int and NoneType

一目了然，看出map是可以接收多個可迭代的參數的，把迭代對象們相同下標的項作為參數傳入到了函數之中。而且短的那個迭代如果沒有值了，就會用None去代替。

當然了，如果函數是None的話，我們將默認用identity函數去處理，這個identity函數呢，其實就是一個返回參數的函數。：

>>> map(None,l1,l2[1:])[(1, 3), (2, 2), (3, 1), (4, None)]

怎麼樣，刺不刺激。

個人感覺map函數就像一個列表生成器一般，是用來迭代處理列表的一種方法

>>> [x*y for x,y in zip(l1,l2)] [4, 6, 6, 4]

但是map有個好處，就是可以傳入lambda表達式，而列表生成器里這樣做就會有問題（只是批量生成函數，而且將變數作為參數傳入lambda,最後再調用lambda函數時，會重新去取變數,可以參看python lambda結合列表推導式?）：

>>> [lambda x,y:x*y for x,y in zip(l1,l2)][<function <lambda> at 0x0000000003884C18>, <function <lambda> at 0x0000000003884C88>, <function <lambda> at 0x0000000003884CF8>, <function <lambda> at 0x0000000003884D68>]

推薦閱讀：