两数相加
题目
给出两个非空的鍊表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
逐位相加法
整数加法可以分解为逐位相加。
举个例子，整数342和465用链表表示为：
链表中每个节点只存储整数中的一位，且低位在前高位在后。
两个链表中相同位置的节点中存储的值，在各自整数中所处的位数也相同。将链表中相同位置节点中的值相加，等同于整数逐位相同。
2加5得7，4加6得0进1，3加4再加进1得8。
代码
package io.github.rscai.leetcode.bytedance.linktree;
public class Solution1022A {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode la = l1;
ListNode lb = l2;
int carry = 0;
ListNode head = null;
ListNode tail = null;
while (la != null || lb != null) {
int aValue = 0;
if (la != null) {
aValue = la.val;
la = la.next;
}
int bValue = 0;
if (lb != null) {
bValue = lb.val;
lb = lb.next;
}
int sum = aValue + bValue + carry;
carry = Math.floorDiv(sum, 10);
ListNode newNode = new ListNode(sum % 10);
if (tail == null) {
head = newNode;
tail = head;
} else {
tail.next = newNode;
tail = newNode;
}
}
if (carry != 0) {
ListNode newNode = new ListNode(carry);
if (tail == null) {
head = newNode;
tail = head;
} else {
tail.next = newNode;
tail = newNode;
}
}
return head;
}
}
复杂度分析
时间复杂度
本演算法同时遍历两个链表，且仅遍历一次。时间复杂度为：
空间复杂度
使用了五个变量。空间复杂度为：