直播截圖

編輯切換為居中

編輯切換為居中

題目描述

給定兩個用鏈表表示的整數(shù)，每個節(jié)點包含一個數(shù)位。 這些數(shù)位是反向存放的，也就是個位排在鏈表首部。 編寫函數(shù)對這兩個整數(shù)求和，并用鏈表形式返回結(jié)果。 示例： 輸入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 輸出：2 -> 1 -> 9，即912

開始解題（python）

編輯切換為居中

def addTwoNumbers(l1, l2): ? ?dummy = ListNode(0) ?# 創(chuàng)建一個虛擬節(jié)點作為新鏈表的頭部 ? ?curr = dummy ?# 用 curr 指針指向當(dāng)前節(jié)點 ? ?carry = 0 ?# 進(jìn)位值 ? ?while l1 or l2: ? ? ? ?# 獲取 l1 和 l2 當(dāng)前位置的數(shù)位，如果已經(jīng)達(dá)到鏈表末尾，則為 0 ? ? ? ?x = l1.val if l1 else 0 ? ? ? ?y = l2.val if l2 else 0 ? ? ? ?# 計算當(dāng)前位置的和，并考慮進(jìn)位 ? ? ? ?# 然后取得個位數(shù)存入新鏈表中 ? ? ? ?sum = x + y + carry ? ? ? ?carry = sum // 10 ? ? ? ?curr.next = ListNode(sum % 10) ? ? ? ?curr = curr.next ? ? ? ?# 移動到下一個節(jié)點 ? ? ? ?if l1: ? ? ? ? ? ?l1 = l1.next ? ? ? ?if l2: ? ? ? ? ? ?l2 = l2.next ? ?# 如果最后還有進(jìn)位，則在新鏈表的最后添加一個節(jié)點 ? ?if carry > 0: ? ? ? ?curr.next = ListNode(carry) ? ?return dummy.next ?# 返回新鏈表的頭部

編輯切換為居中

逐步驗算

編輯切換為居中

編輯切換為居中

首先，我們有兩個輸入鏈表：

l1: 7 -> 1 -> 6

l2: 5 -> 9 -> 2

我們將使用addTwoNumbers函數(shù)來將這兩個鏈表相加，并返回結(jié)果鏈表的頭部。

創(chuàng)建一個虛擬節(jié)點作為新鏈表的頭部：dummy = ListNode(0)，這個節(jié)點的值暫時沒有意義。

創(chuàng)建一個指針 curr，指向當(dāng)前節(jié)點，初始指向虛擬節(jié)點：curr = dummy。

創(chuàng)建一個變量 carry 來表示進(jìn)位值，初始值為 0。

進(jìn)入循環(huán)，直到 l1 和 l2 都遍歷完了。

獲取 l1 和 l2 當(dāng)前位置的數(shù)位，如果已經(jīng)達(dá)到鏈表末尾，則為 0。

對于第一次循環(huán)，x = 7 ?(l1.val)，y = 5 ?(l2.val)。

計算當(dāng)前位置的和，并考慮進(jìn)位。

sum = x + y + carry = 7 + 5 + 0 = 12，carry = sum // 10 = 12 // 10 = 1。

這里的 sum 為兩個數(shù)位的和再加上上一次計算的進(jìn)位。

創(chuàng)建一個新節(jié)點，其值為和的個位數(shù)。

curr.next = ListNode(sum % 10) = ListNode(12 % 10) = ListNode(2)。

這個節(jié)點將會成為新鏈表的下一個節(jié)點，其值為和的個位數(shù)。

將 curr 指針移動到下一個節(jié)點。

curr = curr.next，這樣 curr 指向了新創(chuàng)建的節(jié)點。

移動到下一個節(jié)點。

注意，如果 l1 或 l2 已經(jīng)遍歷完了，則將對應(yīng)的指針設(shè)置為 None。

對于第一次循環(huán)，l1 和 l2 仍然有下一個節(jié)點，所以 l1 和 l2 指針分別向后移動一位。

當(dāng)循環(huán)結(jié)束后，檢查是否還有進(jìn)位。

如果 carry 大于 0，則在新鏈表的最后添加一個節(jié)點。

carry = 1，所以 curr.next = ListNode(carry) = ListNode(1)。

這個節(jié)點的值為進(jìn)位值，將會成為新鏈表的最后一個節(jié)點。

返回新鏈表的頭部：dummy.next。dummy 是一個虛擬節(jié)點，dummy.next 才是真正的鏈表頭部。

所以最后結(jié)果為 2 -> 1 -> 9，即912。

實際應(yīng)用

編輯切換為居中

這個函數(shù)可以用于解決兩個鏈表表示的整數(shù)相加的問題。實際應(yīng)用場景包括但不限于以下情況：

高精度整數(shù)相加：當(dāng)兩個整數(shù)的位數(shù)很大時，常規(guī)的整數(shù)相加操作可能會造成溢出。使用鏈表表示整數(shù)可以避免溢出問題，并且能夠處理任意長的整數(shù)相加。

大數(shù)計算：在某些科學(xué)計算、金融計算或密碼學(xué)等領(lǐng)域中，可能需要進(jìn)行大數(shù)計算，即超過計算機(jī)數(shù)據(jù)類型范圍的數(shù)值計算。鏈表的靈活性使得可以輕松處理大數(shù)計算問題。

數(shù)據(jù)結(jié)構(gòu)的相加：當(dāng)涉及到兩個鏈表或其他數(shù)據(jù)結(jié)構(gòu)的相加時，可以使用類似的思路。通過遍歷兩個數(shù)據(jù)結(jié)構(gòu)，并將對應(yīng)位置的元素相加，可以得到新的數(shù)據(jù)結(jié)構(gòu)。

總之，這個函數(shù)提供了一種通用的方法，用于解決鏈表或其他數(shù)據(jù)結(jié)構(gòu)中表示的數(shù)字相加的問題，可以應(yīng)用于多種實際場景中。

python和python3的異同

編輯切換為居中