Add Two Numbers 兩數(shù)相加
問題描述：
給你兩個 非空 的鏈表，表示兩個非負(fù)的整數(shù)。它們每位數(shù)字都是按照 逆序 的方式存儲的，并且每個節(jié)點只能存儲 一位 數(shù)字。
請你將兩個數(shù)相加，并以相同形式返回一個表示和的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭。
每個鏈表中的節(jié)點數(shù)在范圍 [ 1 , 100 ] 內(nèi) 0 < = N o d e . v a l < = 9 題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo) 0 每個鏈表中的節(jié)點數(shù)在范圍 [1, 100] 內(nèi)\\ 0 <= Node.val <= 9\\ 題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)0 每個鏈表中的節(jié)點數(shù)在范圍[1,100]內(nèi)0<=Node.val<=9題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)0
分析
July 2的daily。比昨天的難度略高，這里的數(shù)值是以鏈表的形式給出。要求2個數(shù)進(jìn)行相加。
以鏈表形式表達(dá)的數(shù)值，它的數(shù)值范圍就可以不受 l o n g long long的限制了。因為最終的結(jié)果也是鏈表。
而對2個數(shù)進(jìn)行相加，一定是從低位開始，這些都是小學(xué)數(shù)學(xué)。
需要注意的是進(jìn)位，如果 s u m = x sum=x sum=x,那么留在當(dāng)前位的數(shù)值就應(yīng)該是 x m o d ?? 10 x \mod 10 xmod10,而進(jìn)位就交給 c a r r y = x / 10. carry = x/10. carry=x/10.
所以每次同一位置的數(shù)值相加，還要把carry計算進(jìn)去。
因為鏈表整體是從低到高的，所以每計算出一個位置，就要把它插入到之前的鏈表結(jié)尾，至于如何操作鏈表，就不說了。
c
u
r
=
a
+
b
+
c
a
r
r
y
,
c
a
r
r
y
=
1
o
r
0
cur = a+b+carry, carry =1 or 0
cur=a+b+carry,carry=1or0
代碼
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p1 = l1,p2 = l2,h = new ListNode(),p = h;
int carry = 0,cur =0;
while(p1!=null||p2!=null){
cur =0;
cur += carry;
if(p1!=null){
cur += p1.val;
p1 = p1.next;
}
if(p2!=null){
cur += p2.val;
p2 = p2.next;
}
int v = cur%10;
carry = cur/10;
ListNode node = new ListNode(v);
p.next = node;
p = p.next;
}
if(carry>0){
p.next = new ListNode(1);
}
return h.next;
}
時間復(fù)雜度 O ( N ) O(N) O(N)
空間復(fù)雜度 O ( 1 ) O(1) O(1)
遞歸方法的也可以做
Tag
MathLinkedList文章來源：http://www.zghlxwxcb.cn/news/detail-515043.html
Recursion文章來源地址http://www.zghlxwxcb.cn/news/detail-515043.html
到了這里，關(guān)于【算法】Add Two Numbers 兩數(shù)相加的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
