【leetcode】两数之和

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

例子

示例 1：

示例 2：

示例 3：

提示：

每个链表中的节点数在范围 [1, 100] 内

0

题目数据保证列表表示的数字不含前导零

V1-简单思路

思路

l1 反转构建为数字

l2 反转构建为数字

num = l1+l2

然后反转列表输出。

坑：这里限定了入参是一个单向链表

java 实现

这里使用 BigInteger，因为位数会比较长，避免超长的情况。

效果

这种是比较慢的。

效果如下[1]

V2-记录进位

思路

每一个节点的值都是 0-9，处理的时候其实我们只需要关心相加是否进位即可。

并不需要这么复杂的把信息处理完相加，从而减少处理时间。

java 实现

说明：这里是自己实现模拟了 BigInteger 的加法。

效果

效果如下[2]：

V3-优化链表遍历

思路

上面的方式中，对于链表的遍历是分别独立进行的。

性能至少有两个优化点：

1）同时遍历两个链表

2）遍历链表的同时，构建节点

内存优化：因为是一边遍历，一边构建节点。所以进位的标识，可以用一个值替代。

java 实现

效果

效果如下[3]：

小结

对于链表的题目，基本都可以先使用笨方法，把节点放点列表中，然后处理，构建结果列表来解决。

但是这种性能基本是最差的。

对于节点的遍历和构建，值得我们进一步思考与学习。

开源地址

为了便于大家学习，所有实现均已开源。欢迎 fork + star~

https://github.com/houbb/leetcode