今日一题LeetCode第二题AddTwoNumbers

　　题目：Youaregiventwononemptylinkedlistsrepresentingtwononnegativeintegers。Thedigitsarestoredinreverseorder，andeachoftheirnodescontainsasingledigit。Addthetwonumbersandreturnthesumasalinkedlist。
　　简言之：两个数相加，这两个数的数据结构以链表的形式给出，例如：754则为457，头结点是4，下面给两个例子：（其中l1、l2分别表示这两个数，即两个链表）
　　例子1：Input：l1〔2，4，3〕，l2〔5，6，4〕Output：〔7，0，8〕Explanation：342465807。
　　例子2：Input：l1〔0〕，l2〔0〕Output：〔0〕
　　分析一波：
　　两个数相加，按照我们小学数学学习的知识，列个竖式，从最低位（个位）开始，两两相加，逢十进一，如图：
　　好了，翻译成JAVA语言试下：
　　初版：classSolution｛publicListNodeaddTwoNumbers（ListNodel1，ListNodel2）｛返回结果，也就是加和后的结果ListNoderetnull；这个是进位，为了让大家好理解，直接用了拼音intjinwei0；l1和l2只要有一个不为空就说明还可以继续加，为空的就直接加0例如7685918则可理解为：7685900018while（l1！nulll2！null）｛获取每一位的数值intn1l1！null？l1。val：0；intn2l2！null？l2。val：0；每一位相加，同时加上进位intsumn1n2jinwei；如果sum大于等于10，说明还得进位jinwei1，同时当前数要减10；否则不进位，jinwei0if（sum10）｛jinwei1；sum10；｝else｛jinwei0；｝好了，组装一下返回值ListNodecurrentnewListNode（sum）；很简单的逻辑，如果ret为空，说明是第一次相加（个位相加），current就是头结点；否则直接往后链即可if（retnull）｛retcurrent；｝else｛ret。nextcurrent；指针也往后移，准备下一位retret。next；｝当前位处理完了，指针往后移，准备处理下一位if（l1！null）｛l1l1。next；｝if（l2！null）｛l2l2。next；｝｝returnret；｝｝
　　这个时候运行了一下，发现ret由于在31行一直后移，最后变成了尾结点，而我们要返回头结点，所以要修改下：
　　修改ret版：增加了3行4行；31行；修改了44行classSolution｛publicListNodeaddTwoNumbers（ListNodel1，ListNodel2）｛返回结果的头指针ListNoderetHeadnull；返回结果，也就是加和后的结果ListNoderetnull；这个是进位，为了让大家好理解，直接用了拼音intjinwei0；l1和l2只要有一个不为空就说明还可以继续加，为空的就直接加0例如7685918则可理解为：7685900018while（l1！nulll2！null）｛获取每一位的数值intn1l1！null？l1。val：0；intn2l2！null？l2。val：0；每一位相加，同时加上进位intsumn1n2jinwei；如果sum大于等于10，说明还得进位jinwei1，同时当前数要减10；否则不进位，jinwei0if（sum10）｛jinwei1；sum10；｝else｛jinwei0；｝好了，组装一下返回值ListNodecurrentnewListNode（sum）；很简单的逻辑，如果ret为空，说明是第一次相加（个位相加），current就是头结点；否则直接往后链即可if（retnull）｛retcurrent；retHeadcurrent；｝else｛ret。nextcurrent；retret。next；｝当前位处理完了，指针往后移，准备处理下一位if（l1！null）｛l1l1。next；｝if（l2！null）｛l2l2。next；｝｝returnretHead；｝｝
　　运行后发现如下case有问题：
　　原来是最高位没有处理，比如999108；目前算法会算成08，因为最后的进位没有处理，知道问题了就好解决了，如果最高位是进位，在处理下：
　　最终版：增加了44行47行classSolution｛publicListNodeaddTwoNumbers（ListNodel1，ListNodel2）｛返回结果的头指针ListNoderetHeadnull；返回结果，也就是加和后的结果ListNoderetnull；这个是进位，为了让大家好理解，直接用了拼音intjinwei0；l1和l2只要有一个不为空就说明还可以继续加，为空的就直接加0例如7685918则可理解为：7685900018while（l1！nulll2！null）｛获取每一位的数值intn1l1！null？l1。val：0；intn2l2！null？l2。val：0；每一位相加，同时加上进位intsumn1n2jinwei；如果sum大于等于10，说明还得进位jinwei1，同时当前数要减10；否则不进位，jinwei0if（sum10）｛jinwei1；sum10；｝else｛jinwei0；｝好了，组装一下返回值ListNodecurrentnewListNode（sum）；很简单的逻辑，如果ret为空，说明是第一次相加（个位相加），current就是头结点；否则直接往后链即可if（retnull）｛retcurrent；retHeadcurrent；｝else｛ret。nextcurrent；retret。next；｝当前位处理完了，指针往后移，准备处理下一位if（l1！null）｛l1l1。next；｝if（l2！null）｛l2l2。next；｝｝最后有进位的话，最高位把1补上if（jinwei1）｛ret。nextnewListNode（1）；｝returnretHead；｝｝
　　最终Accept，结果如下：
　　图片镇题：