【刷题计划】两数相加
1刷题两天小结
很多题目还是直接没有思路，如果只是暴力破解又没有什么作用，有的题目思考很长时间也是做不出来，
刷题顺序也没有什么规律，看到拿到刷哪个，搜了下资料，刷题比较少的可以最开始从头开始刷，目前先按照这个规律刷150题左右
1、建议未刷过题的新人按着顺序来。前 150 题覆盖了很多经典题目和知识点，指针法类如『3 sum』系列，动规类如『regex matching』，搜索类题目如『Sodoku Solver』。 2、基本熟悉知识点（图、树、堆、栈、链表、哈希表、记忆搜索、动态规划、指针法、并查集等）后，可以一类类标签强攻。Leetcode 右侧的标签系统虽然未必 100% 完整，但是大致分类做得还不错。 3、面试前的一个月可以只做『Hard』标签的题目，因为一般两遍之后对于大部分『Medium』难度以下的题目都是肌肉记忆了。多练习『Hard』类题目可以让自己的思路更开阔，因为很多题目使用的奇淫巧技让人惊讶，比如 Leetcode 精心设计连续题号的『84. Largest Rectangle in Histogram』、『85. Maximal Rectangle』。
2今日题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：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]
思路
链表问题一般都会使用虚拟表头来控制循环，类似Java的AQS中哨兵节点，都是为了方便递归或者迭代
这道题目也是这个思路
- 根据最长的链表来控制整体迭代次数
- 添加虚拟节点用于后面建立链表
- 相同index下数字之和，如果某个链表没有这个index，默认给0，不会影响求和，如果是求乘机，默认给1
- 当前链表节点的值为上个节点之和的进位与当前index的两个节点之和，然后再取模，商用来进位
- 当两个链表都迭代完成，如果商数还是大于0, 说明两个链表最后的节点之和大于10，需要继续进位，所以需要多创建一个节点
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//冗余节点，为了循环方便
ListNode preNode = new ListNode(-1);
ListNode currentNode = preNode;
int shang = 0;
//长度以最长的链表为主
while (l1 != null || l2 != null) {
int sum = getSum(l1, l2);
//创建下一个节点
currentNode.next = new ListNode((sum + shang) % 10);
shang = (sum + shang) / 10;
//当前节点指向下一个节点
currentNode = currentNode.next;
//两个链表分别往后迭代
l1 = (l1 == null) ? null : l1.next;
l2 = (l2 == null) ? null : l2.next;
}
//链表长度内加完之后，最后余数还是大于0，说明扩展位数
if (yushu > 0) {
currentNode.next = new ListNode(yushu);
}
return preNode.next;
}
/**
* 节点为null时按照值为0处理
*/
private static int getSum(ListNode l1, ListNode l2) {
int val1 = l1 == null ? 0 : l1.val;
int val2 = l2 == null ? 0 : l2.val;
return val1 + val2;
}
执行用时：2 ms, 在所有 Java 提交中击败了94.18%的用户 内存消耗：38.6 MB, 在所有 Java 提交中击败了61.42%的用户
这道题加上调试，差不多也用了一个多小时，终于AC后感觉还是不错的，
然后再查看下官网的题解
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
while(l1 != null || l2 != null) {
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}
if(carry == 1) {
cur.next = new ListNode(carry);
}
return pre.next;
}
}
执行用时：2 ms, 在所有 Java 提交中击败了94.18%的用户 内存消耗：38.7 MB, 在所有 Java 提交中击败了42.04%的用户
时间和内存几乎一样， 其实整体思路差不多，官网给出了虚拟节点的作用定义：
小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。
同时在其他评论发现了另一个优化点
如果把 carry = sum / 10; 换成 carry = sum >9 ? 1 : 0 ; 这样 速度会快很多
结果：
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：38.5 MB, 在所有 Java 提交中击败了75.16%的用户
这里主要是因为除法运算相对比较耗时的原因，同时题目本身都是整数可以这么特殊处理
类似的优化手段还有位运算替代乘除法等
又是摸鱼+刷题的一天。开心
腾讯云开发者
