1.3 如何計算兩個單鏈表所代表的數(shù)之和

【出自HW筆試題】

難度系數(shù)：★★★☆☆

被考察系數(shù)：★★★★☆

題目描述：

給定兩個單鏈表，鏈表的每個結(jié)點代表一位數(shù)，計算兩個數(shù)的和。例如，輸入鏈表（3→1→5）和鏈表（5→9→2），輸出：8→0→8，即513+295=808，注意個位數(shù)在鏈表頭。

分析與解答：

方法一：整數(shù)相加法

主要思路為：分別遍歷兩個鏈表，求出兩個鏈表所代表的整數(shù)的值，然后把這兩個整數(shù)進(jìn)行相加，最后把它們的和用鏈表的形式表示出來。這種方法的優(yōu)點是計算簡單，但是有個非常大的缺點：當(dāng)鏈表所代表的數(shù)很大時（超出了long int的表示范圍），就無法使用這種方法了。

方法二：鏈表相加法

主要思路為：對鏈表中的結(jié)點直接進(jìn)行相加操作，把相加的和存儲到新的鏈表中對應(yīng)的結(jié)點中，同時還要記錄結(jié)點相加后的進(jìn)位，如下圖所示。

使用這種方法需要注意如下幾個問題：①每組結(jié)點進(jìn)行相加后需要記錄其是否有進(jìn)位；②如果兩個鏈表H1與H2的長度不同（長度分別為L1和L2，且L1＜L2），當(dāng)對鏈表的第L1位計算完成后，接下來只需要考慮鏈表L2剩余的結(jié)點的值（需要考慮進(jìn)位）；③對鏈表所有結(jié)點都完成計算后，還需要考慮此時是否還有進(jìn)位，如果有進(jìn)位，則需要增加新的結(jié)點，此結(jié)點的數(shù)據(jù)域為1。實現(xiàn)代碼如下：

程序的運行結(jié)果為

運行結(jié)果分析：

前5位可以按照整數(shù)相加的方法依次從左到右進(jìn)行計算，第5位7+5+1（進(jìn)位）的值為3，進(jìn)位為1。此時，Head2已經(jīng)遍歷結(jié)束，由于Head1還有結(jié)點沒有被遍歷，所以，依次接著遍歷Head1剩余的結(jié)點：8+1（進(jìn)位）=9，沒有進(jìn)位。因此，運行代碼可以得到上述結(jié)果。

算法性能分析：

由于這種方法需要對兩個鏈表都進(jìn)行遍歷，因此，時間復(fù)雜度為O（N）。其中，N為較長的鏈表的長度，由于計算結(jié)果保存在一個新的鏈表中，因此，空間復(fù)雜度也為O（N）。