題目出處

來自于leetcode

題目描述

You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解讀

給定兩個(gè)表示兩個(gè)非負(fù)整數(shù)的單鏈表，這兩個(gè)數(shù)按反序保存在單鏈表中，把兩個(gè)數(shù)相加并返回一個(gè)單鏈表。
給定的例子為342 + 465 = 807

第一版答案

1. 從兩個(gè)單鏈表的開頭相加，記住進(jìn)位；
2. 幾個(gè)邊界條件需要注意：

• 入?yún)⒌膬蓚€(gè)單鏈表有可能為空，若一個(gè)為空，則直接返回另一個(gè)即可；
• 兩個(gè)單鏈表長(zhǎng)度可能不一樣，在相加結(jié)束后需要把比較長(zhǎng)的剩余的數(shù)值拷貝過去；
• 進(jìn)位也需要考慮，如5 + 5 = 10， 當(dāng)兩個(gè)單鏈表處理完畢后，如果還有進(jìn)位，還需要增加一個(gè)節(jié)點(diǎn)

代碼如下

# 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
        """
        if not l1:
            return l2
        if not l2:
            return l1
           
        carry = 0
        sums = l1.val + l2.val + carry
        carry = sums / 10
        res = ListNode(sums % 10)
        l1 = l1.next
        l2 = l2.next
       
        node  = res
        while l1 and l2:
            sums = l1.val + l2.val + carry
            tmp = ListNode(sums % 10)
            carry = sums / 10
           
            node.next = tmp
            node = node.next
            l1 = l1.next
            l2 = l2.next
           
        while l1:
            sums = l1.val + carry
            tmp = ListNode(sums % 10)
            carry = sums / 10
           
            node.next = tmp
            node = node.next
            l1 = l1.next
           
        while l2:
            sums = l2.val + carry
            tmp = ListNode(sums % 10)
            carry = sums / 10
           
            node.next = tmp
            node = node.next
            l2 = l2.next
       
        while carry:
            tmp = ListNode(carry % 10)
            carry = carry / 10
           
            node.next = tmp
            node = node.next
           
        return res

第二版答案

第一版答案中的代碼不夠精煉，從以下兩個(gè)地方入手：

1. 入?yún)⑴袛?，?duì)l1和l2的檢查上，先定義一個(gè)頭節(jié)點(diǎn)，返回頭節(jié)點(diǎn)的next，這樣可以避免處理l1或l2為空的情形，將鏈表中所有的節(jié)點(diǎn)一視同仁進(jìn)行處理；
2. 將四個(gè)while語句合并處理

代碼如下：

# 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
        """
        head = ListNode(0)
           
        carry = 0
        node  = head
        while l1 or l2 or carry:
            val1, val2 = 0, 0
            if l1:
                val1 = l1.val
                l1 = l1.next
           
            if l2:
                val2 = l2.val
                l2 = l2.next
               
            sums = val1 + val2 + carry
            tmp = ListNode(sums % 10)
            carry = sums / 10
           
            node.next = tmp
            node = node.next
           
        return head.next

代碼簡(jiǎn)潔了許多，由于增加了比較多的比較，效率會(huì)稍微下降點(diǎn)。