漫畫：為啥各廠都喜歡考鏈表的加法？

各數(shù)據(jù)結(jié)構(gòu)中的“加減乘除”都是很愛(ài)考察的內(nèi)容。

不了解哨兵節(jié)點(diǎn)的可以看下：

漫畫：刪除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn)（修改版）

好了，了解了哨兵節(jié)點(diǎn)，其實(shí)這道題和哨兵節(jié)點(diǎn)并沒(méi)有什么毛線關(guān)系，我只是讓你復(fù)習(xí)一下（會(huì)不會(huì)想打我）?，F(xiàn)在開始正式分析題目。

老樣子，我們還是先畫圖，假若我們的鏈表是 (2 -> 4 -> 3) + (5 -> 6 -> 4) ，大概就是這樣（注意，這里我們其實(shí)是要完成 342 + 465）：

加法肯定是從最低位到最高位進(jìn)行相加，也就是這里的鏈表頭到鏈表尾進(jìn)行相加，所以需要遍歷鏈表。我們令 l1 和 l2 指向兩個(gè)鏈表的頭，用一個(gè) tmp 值來(lái)存儲(chǔ)同一位相加的結(jié)果，以及一個(gè)新的鏈表來(lái)存儲(chǔ) tmp 的值。（為什么不直接用新鏈表存儲(chǔ)結(jié)果，而是用 tmp 先存儲(chǔ)結(jié)果，再用新鏈表存儲(chǔ) tmp 的值呢？請(qǐng)繼續(xù)往下看）

記住：所有模擬運(yùn)算的題目，都需要考慮進(jìn)位。這里因?yàn)閭€(gè)位不涉及進(jìn)位，開始計(jì)算十位。我們同時(shí)遍歷 l1，l2，以及新鏈表到下一位。

重復(fù)上面的操作，可以看到十位與個(gè)位不同，發(fā)生了進(jìn)位。這時(shí)，剛才的 tmp 就有了用武之地。我們使用 tmp 攜帶進(jìn)位的值到下一位的運(yùn)算。自然，這里的鏈表也不能直接存儲(chǔ) tmp 的值了，而是要存儲(chǔ) tmp%10 的值。重復(fù)這個(gè)步驟，直到兩個(gè)鏈表都遍歷完成，并且 tmp 沒(méi)有進(jìn)位值：

現(xiàn)在只需要返回我們的新鏈表就可以了。問(wèn)題來(lái)了，因?yàn)槲覀儧](méi)有構(gòu)造哨兵節(jié)點(diǎn)，所以此時(shí)不太容易直接返回新鏈表。所以在整個(gè)流程的第一步，我們還需要用一個(gè)哨兵節(jié)點(diǎn)指向我們的新鏈表。

分析完畢，直接上代碼（好久沒(méi)翻Go的牌子了）：

 1//Go
 2func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
 3    list := &ListNode{0, nil}
 4    //這里用一個(gè)result，只是為了后面返回節(jié)點(diǎn)方便，并無(wú)他用
 5    result := list
 6    tmp := 0
 7    for l1 != nil || l2 != nil || tmp != 0 {
 8        if l1 != nil {
 9            tmp += l1.Val
10            l1 = l1.Next
11        }
12        if l2 != nil {
13            tmp += l2.Val
14            l2 = l2.Next
15        }
16        list.Next = &ListNode{tmp % 10, nil}
17        tmp = tmp / 10
18        list = list.Next
19    }
20    return result.Next
21}

（還湊合）

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝