0002. 两数相加 #
- 标签:链表
- 难度:容易
一、题目说明 #
描述:给定两个非空的链表 l1
和 l2
。分别用来表示两个非负整数,每位数字都是按照逆序的方式存储的,每个节点存储一位数字。
要求:计算两个非负整数的和,并逆序返回表示和的链表。
说明:
- 每个链表中的节点数在范围 $[1, 100]$ 内。
- $0 \le Node.val \le 9$。
- 题目数据保证列表表示的数字不含前导零。
示例:
- 示例 1:
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.
- 示例 2:
输入:l1 = [0], l2 = [0]
输出:[0]
二、解题思路 #
1. 数学计算 #
感觉这道题目,考察细心多于算法,因为这个题目的编码逻辑,就是数学加法运算的抽象。
- 从个位开始,将两个个位数进行相加,得出结果为个位,如果有进位,则记录进位;
- 然后是十位,继续上述逻辑;
- 直到两个数字的所有位都计算完毕,得出最终结果。
需要特别注意的是:
- 两个数字的长度很可能不一致,所以需要用0来补位计算;
- 计算完毕之后,需要注意是否有进位;
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode step = result;
//进位
int carry = 0;
while(l1!=null || l2!=null){
int a = null==l1 ? 0 : l1.val;
int b = null==l2 ? 0 : l2.val;
int sum = a + b + carry;
carry = sum / 10;
step.next = new ListNode(sum % 10);
step = step.next;
l1 = null==l1 ? null : l1.next;
l2 = null==l2 ? null : l2.next;
}
if(carry!=0){
step.next = new ListNode(carry);
}
return result.next;
}