這個(gè)題目?jī)?nèi)容是給定兩個(gè)非空鏈表,每個(gè)鏈表表示一個(gè)非負(fù)整數(shù),鏈表的每個(gè)節(jié)點(diǎn)存儲(chǔ)整數(shù)的一位,且鏈表頭為最高位,鏈表尾為最低位.求兩個(gè)鏈表表示的整數(shù)相加后的結(jié)果,值也用一個(gè)鏈表表示.

例如:

    Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
    Output: 7 -> 8 -> 0 -> 7

升級(jí)版

如果不允許將鏈表翻轉(zhuǎn),應(yīng)該如何解決

我的思路

由于鏈表正向表示一個(gè)整數(shù),所以和我們大腦算數(shù)的思維方式相同,那就按照直觀的思路去計(jì)算,先得到加法結(jié)果,然后再將結(jié)果優(yōu)化為題目要求的鏈表即可.

即:

    加數(shù):   (7 -> 2 -> 4 -> 3 )
    被加數(shù):      ( 5 -> 6 -> 4 )
    初步結(jié)果:(7 -> 7 ->10 -> 7 )  // 有進(jìn)位
    化簡(jiǎn)后:  (7 -> 8 -> 0 -> 7 )

細(xì)節(jié)思考1

按照我上面舉的例子,有一個(gè)默認(rèn)條件,就是兩個(gè)鏈表中假設(shè)第一個(gè)鏈表長(zhǎng)度最長(zhǎng),這樣就可以完全按照例子中的思路來(lái)進(jìn)行處理.但是實(shí)際題目給出的鏈表不一定遵循這個(gè)規(guī)則,所以第一步要計(jì)算兩個(gè)鏈表的長(zhǎng)度,并以最長(zhǎng)的鏈表為基礎(chǔ)進(jìn)行計(jì)算,將計(jì)算結(jié)果存在最長(zhǎng)鏈表中,這樣可以在計(jì)算初步結(jié)果時(shí)不用考慮申請(qǐng)新節(jié)點(diǎn)問(wèn)題.

細(xì)節(jié)思考2

相加的過(guò)程不用細(xì)說(shuō),設(shè)較長(zhǎng)鏈表長(zhǎng)度為 l1,短鏈表長(zhǎng)度為 l2.則相加過(guò)程為在長(zhǎng)鏈表上第(l1-l2)個(gè)位置開(kāi)始,逐個(gè)節(jié)點(diǎn)計(jì)算兩個(gè)鏈表每個(gè)節(jié)點(diǎn)的和,直到最后一個(gè)節(jié)點(diǎn).加完就得到了初步結(jié)果,然后再進(jìn)行簡(jiǎn)化.應(yīng)該能看出,這個(gè)方法的難點(diǎn)就是在簡(jiǎn)化初步結(jié)果這里.因?yàn)殒湵硎钦虮硎疽粋€(gè)整數(shù),而按照進(jìn)位思路是節(jié)點(diǎn)N的下一個(gè)節(jié)點(diǎn)進(jìn)位到節(jié)點(diǎn)N,但是鏈表又是單向鏈表,只能順序訪問(wèn)到下個(gè)節(jié)點(diǎn),不能訪問(wèn)到上個(gè)節(jié)點(diǎn).

所以,問(wèn)題來(lái)了:如何獲取下一個(gè)節(jié)點(diǎn)是否需要向前進(jìn)位,并在本節(jié)點(diǎn)上加1.

這個(gè)問(wèn)題,其實(shí)還暗含著幾個(gè)小的細(xì)節(jié),下面我再拆開(kāi)解釋我的思考過(guò)程.

1.獲取下一節(jié)點(diǎn)是否需要進(jìn)位,在當(dāng)前節(jié)點(diǎn)是否加1

這個(gè)問(wèn)題簡(jiǎn)單,只有弄兩個(gè)指針就好了,第一個(gè)指向當(dāng)前待優(yōu)化節(jié)點(diǎn),第二個(gè)指向下一個(gè)節(jié)點(diǎn),用了輔助判斷是否下一位有進(jìn)位,兩個(gè)指針同時(shí)像后移動(dòng),終止條件是第二個(gè)節(jié)點(diǎn)等于NULL.

2.進(jìn)位具有傳遞性

當(dāng)你判斷下一節(jié)點(diǎn)需要進(jìn)位并在當(dāng)前節(jié)點(diǎn)上面加1的時(shí)候,由于進(jìn)位的傳遞性,有可能出現(xiàn)當(dāng)前節(jié)點(diǎn)在加1操作之后也具有了進(jìn)位,比如當(dāng)前節(jié)點(diǎn)本來(lái)是9,下一節(jié)點(diǎn)又需要進(jìn)位,所以當(dāng)前節(jié)點(diǎn)的值就變成了10,但是此時(shí)指針已經(jīng)指向了這個(gè)節(jié)點(diǎn),不能再找到它的上一個(gè)節(jié)點(diǎn)去加1.所以每一輪優(yōu)化過(guò)程只能保證從尾節(jié)點(diǎn)倒數(shù)開(kāi)始的第N節(jié)點(diǎn)已經(jīng)得到化簡(jiǎn),至于整個(gè)鏈表中是否都已經(jīng)完成化簡(jiǎn),并不能確定,只有在進(jìn)行了 l1次優(yōu)化過(guò)程之后才能完全保證除了頭節(jié)點(diǎn)之外的其他節(jié)點(diǎn)都已經(jīng)符合題目要求了.所以這里可以用一個(gè)循環(huán)對(duì)鏈表進(jìn)行多次優(yōu)化,來(lái)保證整個(gè)鏈表都已經(jīng)得到了化簡(jiǎn).
當(dāng)然,也可以取個(gè)巧,我設(shè)置了一個(gè)flag,初始化為真,每次循環(huán)開(kāi)始時(shí)置為假,然后進(jìn)行一輪化簡(jiǎn),如果化簡(jiǎn)過(guò)程中發(fā)生了一次進(jìn)位操作,那就要把flag置為真,以保證再進(jìn)行一輪化簡(jiǎn),直到一輪化簡(jiǎn)下來(lái)都沒(méi)有進(jìn)行進(jìn)位的時(shí)候,我就可以認(rèn)為整個(gè)鏈表除頭節(jié)點(diǎn)外都已經(jīng)滿足題目的要求,可以不用進(jìn)行繼續(xù)化簡(jiǎn)了,此時(shí)flag為假,跳出循環(huán).

3.頭節(jié)點(diǎn)的處理

在解決完第2個(gè)問(wèn)題之后,容易發(fā)現(xiàn),我并沒(méi)有對(duì)頭節(jié)點(diǎn)進(jìn)行化簡(jiǎn),因?yàn)槿绻^節(jié)點(diǎn)要進(jìn)位的話,還需要申請(qǐng)新節(jié)點(diǎn),這和其他節(jié)點(diǎn)的進(jìn)位操作是不同的,所以我在最后單獨(dú)對(duì)頭節(jié)點(diǎn)進(jìn)行化簡(jiǎn),如果頭節(jié)點(diǎn)需要進(jìn)位的話就申請(qǐng)一個(gè)新節(jié)點(diǎn),然后進(jìn)行化簡(jiǎn),如果不需要進(jìn)位則整個(gè)步驟完成,直接返回當(dāng)前頭節(jié)點(diǎn)即可.