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

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

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

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

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

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

記住：所有模擬運算的題目，都需要考慮進位。這里因為個位不涉及進位，開始計算十位。我們同時遍歷 l1，l2，以及新鏈表到下一位。

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

現(xiàn)在只需要返回我們的新鏈表就可以了。問題來了，因為我們沒有構造哨兵節(jié)點，所以此時不太容易直接返回新鏈表。所以在整個流程的第一步，我們還需要用一個哨兵節(jié)點指向我們的新鏈表。

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

 1//Go
 2func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
 3    list := &ListNode{0, nil}
 4    //這里用一個result，只是為了后面返回節(jié)點方便，并無他用
 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}

（還湊合）

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