點擊 這里 可以查看更多算法面試相關(guān)內(nèi)容~
題目描述
給你兩個非空的鏈表，表示兩個非負(fù)的整數(shù)若未。它們每位數(shù)字都是按照逆序的方式存儲的毕莱，并且每個節(jié)點只能存儲一位數(shù)字票顾。
請你將兩個數(shù)相加，并以相同形式返回一個表示和的鏈表。
你可以假設(shè)除了數(shù)字 0 之外隧土，這兩個數(shù)都不會以 0 開頭。
示例 1：
輸入：l1 = [2,4,3], l2 = [5,6,4] 輸出：[7,0,8]
解釋：342 + 465 = 807.
示例 2：
輸入：l1 = [0], l2 = [0] 輸出：[0]
示例 3：
輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 輸出：[8,9,9,9,0,0,0,1]
提示：
- 每個鏈表中的節(jié)點數(shù)在范圍 [1, 100] 內(nèi)
0 <= Node.val <= 9- 題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零
樸素解法（哨兵技巧）
這是道模擬題命爬，模擬人工豎式做加法的過程：
從最低位至最高位曹傀，逐位相加，如果和大于等于 10饲宛，則保留個位數(shù)字皆愉，同時向前一位進(jìn) 1 如果最高位有進(jìn)位，則需在最前面補 1艇抠。
做有關(guān)鏈表的題目幕庐，有個常用技巧：添加一個虛擬頭結(jié)點（哨兵），幫助簡化邊界情況的判斷家淤。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tmp = dummy;
int t = 0;
while (l1 != null || l2 != null) {
int a = l1 != null ? l1.val : 0;
int b = l2 != null ? l2.val : 0;
t = a + b + t;
tmp.next = new ListNode(t % 10);
t /= 10;
tmp = tmp.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (t > 0) tmp.next = new ListNode(t);
return dummy.next;
}
}
時間復(fù)雜度：m 和 n 分別代表兩條鏈表的長度异剥，則遍歷到的最遠(yuǎn)位置為 ，復(fù)雜度為
空間復(fù)雜度：創(chuàng)建了 max(m,n) + 1 個節(jié)點（含哨兵）絮重，復(fù)雜度為 （忽略常數(shù)）
注意：事實上還有可能創(chuàng)建 + 2 個節(jié)點冤寿，包含哨兵和最后一位的進(jìn)位。但復(fù)雜度仍為
青伤。
最后
這是我們「刷穿 LeetCode」系列文章的第 No.2 篇督怜，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目潮模，部分是有鎖題亮蛔，我們將先將所有不帶鎖的題目刷完。
在這個系列文章里面擎厢，除了講解解題思路以外究流，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應(yīng)的代碼模板动遭。
由于 LeetCode 的題目隨著周賽 & 雙周賽不斷增加芬探，為了方便我們統(tǒng)計進(jìn)度，我們將按照系列起始時的總題數(shù)作為分母厘惦，完成的題目作為分子偷仿，進(jìn)行進(jìn)度計算哩簿。當(dāng)前進(jìn)度為 2/1916 。
為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼酝静，我建立了相關(guān)的倉庫：Github 地址 & Gitee 地址节榜。
在倉庫地址里，你可以看到系列文章的題解鏈接别智、系列文章的相應(yīng)代碼宗苍、LeetCode 原題鏈接和一些其他的優(yōu)選題解。
