算法：兩數(shù)相加

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

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

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

示例

思路與算法

首先，我們按照示例中的結(jié)果發(fā)現(xiàn)我們可以同時(shí)遍歷這兩個(gè)鏈表，按照同一方向，相同的位置的數(shù)字進(jìn)行類加

舉例說明：

n1、n2代表兩個(gè)鏈表相同位置的值，carry代表進(jìn)位值。最終結(jié)果的鏈表的相同位置的值為 (n1 + n2 + carry) % 10 ，新的進(jìn)位值為（n1 + n2 + carry）/ 10。

如果兩個(gè)鏈表的長度不同，則可以認(rèn)為短的鏈表的后面有若干個(gè) 0 。

最后，如果鏈表遍歷結(jié)束后，如果carry > 0，那還需要在最后的鏈表上再附加一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的值為 carry。

代碼如下：

時(shí)間復(fù)雜度：O(max(m,n))，其中 m 和 n 分別為兩個(gè)鏈表的長度。我們要遍歷兩個(gè)鏈表的全部位置，而處理每個(gè)位置只需要 O(1) 的時(shí)間。
空間復(fù)雜度：O(1)。注意返回值不計(jì)入空間復(fù)雜度。

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。

標(biāo)簽：