2. 兩數(shù)相加 - 力扣（LeetCode）

可以參考的B站視頻講解鏈接兩數(shù)相加

1 題目

給你兩個(gè) 非空 的鏈表，表示兩個(gè)非負(fù)的整數(shù)。它們每位數(shù)字都是按照 逆序 的方式存儲(chǔ)的，并且每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。

請(qǐng)你將兩個(gè)數(shù)相加，并以相同形式返回一個(gè)表示和的鏈表。

你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭。

示例 1：

輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807.

示例 2：

輸入：l1 = [0], l2 = [0]
輸出：[0]

示例 3：

輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]

2 解題

這個(gè)題目最大的難點(diǎn)其實(shí)不是思路上的問(wèn)題，而是對(duì)于自定義的單鏈表ListNode的理解和使用問(wèn)題。現(xiàn)在就將ListNode類進(jìn)行適當(dāng)?shù)慕忉尯褪褂谩?/p>

單鏈表ListNode

首先ListNoded的定義代碼是下面這個(gè)class。

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

1. 類定義

• class ListNode: 定義了一個(gè)名為ListNode的類，表示鏈表中的一個(gè)節(jié)點(diǎn)

2. 構(gòu)造函數(shù) __init__

• 這是類的初始化方法，在創(chuàng)建新節(jié)點(diǎn)時(shí)自動(dòng)調(diào)用
• 有兩個(gè)參數(shù)，都有默認(rèn)值：
  • val=0：節(jié)點(diǎn)的值，默認(rèn)為0
  • next=None：指向下一個(gè)節(jié)點(diǎn)的指針，默認(rèn)為None（表示沒(méi)有下一個(gè)節(jié)點(diǎn)）

3. 屬性

• self.val：存儲(chǔ)當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)值
• self.next：存儲(chǔ)對(duì)下一個(gè)節(jié)點(diǎn)的引用（指針）

4.需要注意的地方

• self.val僅僅表示的是當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)值而非所有的數(shù)據(jù)值

• 這個(gè)和數(shù)組是完全不一樣的使用方法，他的只有通過(guò)遍歷整個(gè)鏈表才能進(jìn)行相應(yīng)的節(jié)點(diǎn)位置的判定。

知道了ListNOde的用法之后便可以進(jìn)行程序的編寫了。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        if l1 is None :
            return l2
        if l2 is None:
            return l1
        
        prehead = ListNode(0) #創(chuàng)建一個(gè)val為0的單節(jié)點(diǎn)
        head = prehead #指針開(kāi)始的地方
        carry = 0

        while l1 and l2: #同時(shí)
            retain = (l1.val + l2.val + carry)%10
            carry = (l1.val + l2.val + carry )//10
            head.next = ListNode(retain)
            l1 = l1.next
            l2 = l2.next
            head = head.next
        
        while l1: # l1 too long
            retain = (l1.val +carry)%10
            carry = (l1.val +carry)//10
            head.next = ListNode(retain)
            l1 = l1.next
            head = head.next
        
        while l2 :
            retain = (l2.val + carry)%10
            carry = (l2.val + carry)//10
            head.next = ListNode(retain)
            l2 = l2.next
            head = head.next
        
        if carry == 1:
            head.next  = ListNode(carry)

        return prehead.next