題目描述
給你兩個非空的鏈表勉耀，表示兩個非負(fù)的整數(shù)。它們每位數(shù)字都是按照逆序的方式存儲的仗阅，并且每個節(jié)點(diǎn)只能存儲一位數(shù)字。
請你將兩個數(shù)相加国夜，并以相同形式返回一個表示和的鏈表减噪。
你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭车吹。
示例 1：
image.png
輸入：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é)點(diǎn)數(shù)在范圍 [1, 100] 內(nèi)
- 0 <= Node.val <= 9
- 題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零
解題思路
- 創(chuàng)建一個新的鏈表筹裕，用于存儲兩個數(shù)相加的結(jié)果。
- 初始化兩個指針窄驹，分別指向兩個鏈表的頭部朝卒。
- 創(chuàng)建一個變量carry，用于存儲進(jìn)位值乐埠，初始值為0抗斤。
- 遍歷兩個鏈表，直到兩個鏈表都遍歷完丈咐。
- 在每一位上瑞眼，將兩個鏈表對應(yīng)位置的數(shù)字相加，并加上進(jìn)位值carry棵逊。
- 將相加的結(jié)果對10取余伤疙，得到當(dāng)前位的值，并更新進(jìn)位值carry為相加結(jié)果除以10的商歹河。
- 將當(dāng)前位的值添加到新鏈表中掩浙。
- 將兩個指針向后移動一位，繼續(xù)下一位的相加秸歧。
- 如果兩個鏈表中有一個鏈表已經(jīng)遍歷完厨姚，而另一個鏈表還有剩余的數(shù)字，則將剩余的數(shù)字與進(jìn)位值相加键菱，并將結(jié)果添加到新鏈表中谬墙。
- 如果最后的進(jìn)位值不為0，則將進(jìn)位值添加到新鏈表的末尾经备。
- 返回新鏈表作為結(jié)果拭抬。
題目解答
public class LeetCode0002 {
public static void main(String[] args) {
LeetCode0002 leetCode0002 = new LeetCode0002();
ListNode l1 = new ListNode(2);
l1.next = new ListNode(4);
l1.next.next = new ListNode(3);
ListNode l2 = new ListNode(5);
l2.next = new ListNode(6);
l2.next.next = new ListNode(4);
ListNode res = leetCode0002.addTwoNumbers(l1, l2);
res.print();
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
int ten = 0;
while (l1 != null || l2 != null) {
int v1 = l1 != null ? l1.val : 0;
int v2 = l2 != null ? l2.val : 0;
int sum = v1 + v2 + ten;
ten = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (ten != 0) {
cur.next = new ListNode(ten);
}
return dummy.next;
}
}
運(yùn)行結(jié)果
image.png
