2. 兩數(shù)相加
給定兩個(gè)非空鏈表來(lái)表示兩個(gè)非負(fù)整數(shù)。位數(shù)按照逆序方式存儲(chǔ)，它們的每個(gè)節(jié)點(diǎn)只存儲(chǔ)單個(gè)數(shù)字。將兩數(shù)相加返回一個(gè)新的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)字都不會(huì)以零開(kāi)頭。
示例:
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

解法1:

常規(guī)思路, 關(guān)鍵點(diǎn): 頭結(jié)點(diǎn), 進(jìn)位, 鏈表長(zhǎng)度不一致時(shí)

class Solution:
    def addTwoNumbers(self, l1, l2):
        carry = 0  #進(jìn)位值
        isFirst = True  #頭結(jié)點(diǎn)flag
        currentNode = None  #當(dāng)前結(jié)點(diǎn)
        head = None  #頭結(jié)點(diǎn)
        while (l1 or l2 or carry != 0): #循環(huán)條件: l1, l2的遍歷沒(méi)結(jié)束, 或有高位進(jìn)位時(shí)
            val1 = 0
            val2 = 0
            if l1:
                val1 = l1.val
                l1 = l1.next
            if l2:
                val2 = l2.val
                l2 = l2.next
            unit = val1 + val2 + carry
            if unit >= 10:
                carry = 1
                unit = unit%10
            else:
                carry = 0
            
            node =  ListNode(unit)
            if isFirst:
                currentNode = node
                head = currentNode
                isFirst = False
            else:
                currentNode.next = node
                currentNode = currentNode.next
        return head

解法2

給定一個(gè)空的頭結(jié)點(diǎn), 簡(jiǎn)化代碼.

class Solution:
    def addTwoNumbers(self, l1, l2):
        head = ListNode(0)  #頭結(jié)點(diǎn)設(shè)為空結(jié)點(diǎn)
        current = head
        carry = 0
        while (l1 or l2 or carry !=0):
            if l1:
                carry += l1.val
                l1 = l1.next
            if l2:
                carry += l2.val
                l2 = l2.next
            node = ListNode(carry%10)
            carry = carry//10
            current.next = node
            current = current.next

        return head.next