本文描述的是我自己的一個(gè)失敗的挑戰(zhàn)經(jīng)歷。
題目
兩個(gè)單鏈表（singly linked list），每一個(gè)節(jié)點(diǎn)里面一個(gè)0-9的數(shù)字， 輸入就相當(dāng)于兩個(gè)大數(shù)了。然后返回這兩個(gè)數(shù)的和（一個(gè)新list）。這兩個(gè)輸入的list 長度相等。 要求是：1. 不用遞歸。2. 要求算法在最好的情況下，只遍歷兩個(gè)list一次， 最差的情況下兩遍。
我的算法是： 2次遍歷是肯定能的，第一次相加并以倒序存，第二次進(jìn)位并倒序。一次/兩次的算法，用2個(gè)指針，一個(gè)指錢一個(gè)，另一個(gè)指向再前一個(gè)，另一個(gè)flag標(biāo)志是否走第二輪。只有前前位有進(jìn)位flag置true跑第二次。
為啥當(dāng)時(shí)會(huì)有這樣的想法呢？因?yàn)樗袛?shù)字都是0～9，所以我假設(shè)了第一輪的相加和進(jìn)位能把大部分該進(jìn)位的都進(jìn)了，所以如果存在需要第二輪的話，找出那個(gè)條件就好了。當(dāng)時(shí)就沿著這個(gè)思路走了。當(dāng)然大部分情況下這個(gè)算法是可行的，但是這里有個(gè)很明顯的漏洞，當(dāng)時(shí)被勝利沖昏頭腦的我怎么會(huì)想的到呢？就是一開始沒有出現(xiàn)進(jìn)位，后來連續(xù)進(jìn)位的情況，如
@趙小罡這位朋友設(shè)計(jì)的用例 1000001+9999999。一并感謝其他指出錯(cuò)誤的網(wǎng)友。
如果有人想懷著鄙視的心態(tài)看下我錯(cuò)誤的代碼，請點(diǎn)擊“
另外有個(gè)高手做了一個(gè)算法，總是只要一次就能搞定的。@hawstein詳情見“
求兩個(gè)單鏈表的和” 尼害的不得了。他的網(wǎng)站上還有不少好東西呢。對于他的算法，我有個(gè)改進(jìn)的建議就是，以他的算法完全沒有必要單獨(dú)考慮第一個(gè)節(jié)點(diǎn)的情況，在遍歷結(jié)束后，判斷下第一個(gè)節(jié)點(diǎn)是否大于9就OK了，如果大于9，最前面插入一個(gè)節(jié)點(diǎn)。