这个题目内容是给定两个非空链表,每个链表表示一个非负整数,链表的每个节点存储整数的一位,且链表头为最高位,链表尾为最低位.求两个链表表示的整数相加后的结果,值也用一个链表表示.
例如:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
升级版
如果不允许将链表翻转,应该如何解决
我的思路
由于链表正向表示一个整数,所以和我们大脑算数的思维方式相同,那就按照直观的思路去计算,先得到加法结果,然后再将结果优化为题目要求的链表即可.
即:
加数: (7 -> 2 -> 4 -> 3 )
被加数: ( 5 -> 6 -> 4 )
初步结果:(7 -> 7 ->10 -> 7 ) // 有进位
化简后: (7 -> 8 -> 0 -> 7 )
细节思考1
按照我上面举的例子,有一个默认条件,就是两个链表中假设第一个链表长度最长,这样就可以完全按照例子中的思路来进行处理.但是实际题目给出的链表不一定遵循这个规则,所以第一步要计算两个链表的长度,并以最长的链表为基础进行计算,将计算结果存在最长链表中,这样可以在计算初步结果时不用考虑申请新节点问题.
细节思考2
相加的过程不用细说,设较长链表长度为 l1,短链表长度为 l2.则相加过程为在长链表上第(l1-l2)个位置开始,逐个节点计算两个链表每个节点的和,直到最后一个节点.加完就得到了初步结果,然后再进行简化.应该能看出,这个方法的难点就是在简化初步结果这里.因为链表是正向表示一个整数,而按照进位思路是节点N的下一个节点进位到节点N,但是链表又是单向链表,只能顺序访问到下个节点,不能访问到上个节点.
所以,问题来了:如何获取下一个节点是否需要向前进位,并在本节点上加1.
这个问题,其实还暗含着几个小的细节,下面我再拆开解释我的思考过程.
1.获取下一节点是否需要进位,在当前节点是否加1
这个问题简单,只有弄两个指针就好了,第一个指向当前待优化节点,第二个指向下一个节点,用了辅助判断是否下一位有进位,两个指针同时像后移动,终止条件是第二个节点等于NULL.
2.进位具有传递性
当你判断下一节点需要进位并在当前节点上面加1的时候,由于进位的传递性,有可能出现当前节点在加1操作之后也具有了进位,比如当前节点本来是9,下一节点又需要进位,所以当前节点的值就变成了10,但是此时指针已经指向了这个节点,不能再找到它的上一个节点去加1.所以每一轮优化过程只能保证从尾节点倒数开始的第N节点已经得到化简,至于整个链表中是否都已经完成化简,并不能确定,只有在进行了 l1次优化过程之后才能完全保证除了头节点之外的其他节点都已经符合题目要求了.所以这里可以用一个循环对链表进行多次优化,来保证整个链表都已经得到了化简.
当然,也可以取个巧,我设置了一个flag,初始化为真,每次循环开始时置为假,然后进行一轮化简,如果化简过程中发生了一次进位操作,那就要把flag置为真,以保证再进行一轮化简,直到一轮化简下来都没有进行进位的时候,我就可以认为整个链表除头节点外都已经满足题目的要求,可以不用进行继续化简了,此时flag为假,跳出循环.
3.头节点的处理
在解决完第2个问题之后,容易发现,我并没有对头节点进行化简,因为如果头节点要进位的话,还需要申请新节点,这和其他节点的进位操作是不同的,所以我在最后单独对头节点进行化简,如果头节点需要进位的话就申请一个新节点,然后进行化简,如果不需要进位则整个步骤完成,直接返回当前头节点即可.
