Kotlin程序员算法宝典：如何计算两个单链表之和

【出自HW笔试题】

难度系数：★★★☆☆ 被考察系数：★★★★☆

题目描述：

给定两个单链表，链表的每个结点代表一位数，计算两个数的和。例如：输入链表（3-＞1-＞5）和链表（5-＞9-＞2），输出：8-＞0-＞8，即513+295=808，注意个位数在链表头。

分析与解答：

方法一：整数相加法

主要思路：分别遍历两个链表，求出两个链表所代表的整数的值，然后把这两个整数进行相加，最后把它们的和用链表的形式表示出来。这种方法的优点是计算简单，但是有个非常大的缺点：当链表所代表的数很大的时候（超出了longint的表示范围），就无法使用这种方法了。

方法二：链表相加法

主要思路：对链表中的结点直接进行相加操作，把相加的和存储到新的链表中对应的结点中，同时还要记录结点相加后的进位。如下图所示：

使用这种方法需要注意以下几个问题：

（1）每组结点进行相加后需要记录其是否有进位。(www.xing528.com)

（2）如果两个链表h1与h2的长度不同（长度分别为L1和L2，且L1＜L2），当对链表的第L1位计算完成后，接下来只需要考虑链表L2剩余的结点的值（需要考虑进位）。

（3）对链表所有结点都完成计算后，还需要考虑此时是否还有进位，如果有进位，则需要增加新的结点，此结点的数据域为1。实现代码如下：

程序的运行结果如下：

Head1：3 4 5 6 7 8

Head2：9 8 7 6 5

相加后：2 3 3 3 3 9

运行结果分析：

前五位可以按照整数相加的方法依次从左到右进行计算，第五位7+5+1（进位）的值为3，进位为1。此时Head2已经遍历结束，由于Head1还有结点没有被遍历，所以，依次接着遍历Head1剩余的结点：8+1（进位）=9，没有进位。因此，运行代码可以得到上述结果。

算法性能分析：

由于这种方法需要对两个链表都进行遍历，因此，时间复杂度为O（N），其中，N为较长的链表的长度，由于计算结果保存在一个新的链表中，因此，空间复杂度也为O（N）。