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