每日一道 LeetCode (45)：两数相加
共 1689字，需浏览 4分钟
·
2020-09-15 09:21
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
代码仓库
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：两数相加
题目来源：https://leetcode-cn.com/problems/add-two-numbers/
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解题方案
先说一下，这道题的难度是中等难度，我又转回去了，从开头顺着往下做题了，昨天实际上题号已经是 200+ 了，我发现接下来的题大多数都变成了 SQL 题和 bash 脚本的题，所以决定返回到最开始，顺着往下做。
这道题看下来感觉不大像是中等难度的题，感觉还没有前两天的二进制数的题难，二进制数的题看了基本属于一脸懵逼的不知道要干什么，这道题读完了以后基本思路是有的。
直接对两个链表进行迭代，然后按位加起来就完了，如果有进位就记录下来，在下次迭代的时候把进位加上去。
因为这道题题目给出来的直接就是逆序的数字，所以直接顺序的从前往后迭代就好了，也没什么滑头。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode curr = pre;
// 定义进位
int carry = 0;
while (l1 != null || l2 != null) {
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int sum = x + y + carry;
// 进位标记
carry = sum / 10;
// 构造下一个节点
curr.next = new ListNode(sum % 10);
// 将指针指向下一个节点
curr = curr.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return pre.next;
}
这个计算方案中需要注意的只有一点，先定义了一个头结点 pre ，至于为什么要定义这个 pre ，因为在下面做迭代的时候，需要移动指针的，如果没有这个 pre 结点，下面迭代的时候指针就动不了了。
然后我去翻了下答案，发现就这一种解法，剩下的都是这种方案的变种解法，要么是定义两个其他的数据结构，比如说队列，先迭代的把数据放到队列里面，然后再迭代队列进行计算。
还有先迭代链表，把这两个整数直接搞成 int 型的，然后再加起来，最后再迭代这个数字转成链表，但是这种方案需要考虑类型溢出的问题，或许可能要搞成 double 类型或者 long 类型的，计算的时候还要注意精度问题。
