面试编程题：单链表和之恋

arron刘

两个单链表（singly linked list），每一个节点里面一个0-9的数字，输入就相当于两个大数了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。 要求是：1. 不用递归。2. 要求算法在最好的情况下，只遍历两个list一次 ，最差的情况下两遍。

bruceteen

这两个输入的list长度相等……2. 要求算法在最好的情况下，只遍历两个list一次 ，最差的情况下两遍。
-------------- 不懂，长度相等，不就是依次遍历一次就行了嘛

arron刘

很简单的从低位到高位啊，要是高位到地位的话，我觉得很复杂的。回复 2# pmerofc


   

l2y3n2

是不是我没看懂题目？

好像直接遍历一次就算出来了啊

arron刘

贴出来瞅瞅回复 6# l2y3n2


   

arron刘

单链表和之恋分析：

原题：两个单链表（singly linked list），每一个节点里面一个0-9的数字，输入就相当于两个大数了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。 要求是：1. 不用递归。2. 要求算法在最好的情况下，只遍历两个list一次 ，最差的情况下两遍。

分析：遇到一个面试题，首先，要澄清和理解题意，确保你的理解和面试官的本意一致。题中的单链表，可不可以原地修改？是从高位到低位，还是低位到高位？如果是从低位到高位，那么问题很简单，是不是？只要两个指针移动（因为是等长的），对应位置相加，同时记录是否有进位，产生的结果存入新的链表中。

如果是从高到低，问题就复杂了，进位是万恶之源。这时，也许我们会想到reverse两个单链表（其实，这也是一道很好的面试题，如何做？考虑递归和递推两种算法），但这样做，是不是最好最坏情形都得遍历两次？好像不合题意。

如果新的链表的节点可以存一个或两个数字，那么，第一遍，将相应节点的数字相加，存入新的链表，并用一个flag标志整个操作中是否有进位。如果没有，结了；否则，再扫描一遍新的链表，将有两个数字的进位存到上一个节点。如果新的链表是双的，问题比较简单；如果新的链表还是单的，这一步也会很复杂，比如，１０－〉９－〉９－〉１２，如何转成１－〉１－〉０－〉０－〉２，本身也是一个很好的面试题。这时可能需要reverse链表再操作。

如果新的链表的节点只能存一个数字，那么能有什么办法？

也许你有更好的解决办法？期待。

dxyf1524

这里的加法是限定了没有负数的存在么？
如果是这样，那就好处理了。
其实在将一个数化成单链表的时候，就可以把数字倒着存放，然后从链表头依次做加法运算，通过一个标志flag来说明是否有进位
类似于 ADDC A，B
如果没有进位，令flag=0，否则flag=1
至于发生进位了，那么将这个节点的数转化一下（通过除以10 的余数0-9，存放），此时flag=1，