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

難度系數：★★★☆☆

被考查系數：★★★★☆

題目描述：

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

分析與解答：

方法一：整數相加法

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

方法二：鏈表相加法

主要思路：對鏈表中的結點直接進行相加操作，把相加的和存儲到新的鏈表中對應的結點中，同時還要記錄結點相加后的進位。如下圖所示：

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

程序的運行結果為

運行結果分析：

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

算法性能分析：

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