牛客網(wǎng)高頻算法題系列-BM11-鏈表相加(二)

題目描述

假設(shè)鏈表中每一個(gè)節(jié)點(diǎn)的值都在 0 - 9 之間，那么鏈表整體就可以代表一個(gè)整數(shù)。給定兩個(gè)這種鏈表，請生成代表兩個(gè)整數(shù)相加值的結(jié)果鏈表。

原題目見：BM11 鏈表相加(二)

解法一：使用棧

首先，特殊情況判斷：

• 如果鏈表一為空，則直接返回鏈表二

• 如果鏈表二為空，則直接返回鏈表一

否則，使用2個(gè)棧用來存放兩個(gè)鏈表的結(jié)點(diǎn)：

• 首先將兩個(gè)鏈表中的結(jié)點(diǎn)添加到棧中；

• 遍歷2個(gè)棧，即執(zhí)行加法，將值添加到新的棧中這樣可以按倒序進(jìn)行結(jié)點(diǎn)值相加，其中需要使用一個(gè)變量記錄進(jìn)位值；

• 需要注意的是，遍歷結(jié)束后，需要根據(jù)進(jìn)位值判斷是否需要添加額外的結(jié)點(diǎn)；

• 最后，根據(jù)新的棧構(gòu)造相加后的鏈表并返回之。

如果不想使用多余的棧空間，可以考慮先將兩個(gè)鏈表倒序排列后，再執(zhí)行加法。

代碼

1.01^{365} ≈ 37.7834343329 ??

0.99^{365} ≈ 0.02551796445 ??

相信堅(jiān)持的力量！