[leetcode algorithms]題目2

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 -> 8Explanation: 342 + 465 = 807.

自己寫的代碼：

首先定義valNext方法，返回當前Node的值，以及next Node。遍歷l1, l2，每次相加的時候如果大於9，則把進位存儲到m中，直到l1，l2都沒有元素，且m=0循環停止。運行時間196 ms。

class Solution: def valNext(self, l): if l: res = l.val l = l.next else: res = 0 return res, l def addTwoNumbers(self, l1, l2): res = ListNode(0) tmp = res m = 0 while l1 or l2 or m: val1, l1 = self.valNext(l1) val2, l2 = self.valNext(l2) k = val1 + val2 + m if k > 9: k -= 10 m = 1 else: m = 0 tmp.next = ListNode(k) tmp = tmp.next return res.next

受討論區啟發後寫的代碼：

思路與我自己想的幾乎一樣，只是用了divmod函數讓代碼更加簡潔。運行時間195 ms。

class Solution: def addTwoNumbers(self, l1, l2): res = tmp = ListNode(0) m = 0 while l1 or l2 or m: if l1: m += l1.val l1 = l1.next if l2: m += l2.val l2 = l2.next tmp.next = ListNode(0) tmp = tmp.next m, tmp.val = divmod(m, 10) return res.next

推薦閱讀：