第二题是把用链表表示的两个数相加。
大概就是操作链表的问题。
题目大意
题目需要将用链表表示的两个数相加。
链表的形式如下：
2 -> 4 -> 3表示342，5 -> 6 -> 4表示564，需要对此输出的是7 -> 0 -> 8，也就是807。
注意事项：一个数除非是0，不会以0开头。也就是不用担心2 -> 4 -> 3 -> 0或者2 -> 4 -> 3 -> 0 -> 0都表示342这种神奇的情况。并且数组总不是空的。
解决方案
我觉得这并不是一道算法题，只是对链表操作的考察。
加法需要考虑的就是进位。
比如上面的例子，低位在链表开头，高位在末端，我们直接往后面加就可以。
首先是2+5，结果是7，进位是0。4+6，在这一位的结果是0，进位是1。那么最后是3+4+1，结果是8。后面都没有了，结束。
我们可以直接修改某个链表上的数值，节省额外的空间。
总之只需要跑完两个链表中较短的长度，结果就出来了。设短的一个链表长度为N，算法的复杂度为$O(N)$。
算法
- 输入为l1, l2两个链表。
- 将结果result指向l1。将进位值inc置为0。新建两个节点s1和s2，并将它们的后继指向l1和l2。
- s1和s2后继节点的值和inc相加，结果存到s1后继节点，后继为空时视为0，如果l1当前是空则创建一个新节点。
- 如果s1后继的值>=0，值取与10的模，inc置为1。否则inc置为0。
- s1和s2分别指向后继节点。
- 如果inc为1或者s1和s2的后继都不为空，到2。否则继续。
- 如果s1后继为空，将它指向s2的后继。
- 返回result。