一、小课堂 - 链表
小课堂开课啦，在这里插播一条重要的知识点 - 数据结构 链表，为今天的算法实现做准备。
此处仅是简要的介绍下链表，以配合算法的实现，后面有专门的文章来详细介绍链表，敬请期待。
链表
链表是一种线性的数据结构，在链表中每个存储的单元我们称之为”节点“，相邻节点之间可以使用特定的引用字段进行链接。
一般一个节点上至少有两个属性：
- 保存了当前节点的值的属性
val
- 保存了下一个节点的引用属性
next
链表有两种类型：
- 单向链表
蓝色箭头指向了下一个节点
- 双向链表
与单向链表不同的是，双向链表中节点上会多一个属性，指向上一个节点
蓝色箭头指向下一个节点，绿色箭头指向上一个节点
创建单向链表：
/** * 声明构造函数 listNode * 节点特征： * val 保存节点的值 * next 保存下一个节点的引用地址 */ function ListNode(val, next) { this.val = (val===undefined ? 0 : val) this.next = (next===undefined ? null : next) } // 当前头节点 const list = new ListNode(23); // 将当前节点指向list let currentNode = list; // 下一个节点 const nextNode = new ListNode(6) // list的next指向了next currentNode.next = nextNode; // 将currentNode的指针指向nextNode currentNode = nextNode; // 下一个节点 const nextNode2 = new ListNode(15); // 将currentNode的指针指向nextNode2 currentNode.next = nextNode2;
链表遍历：
let currentNode = list; do { // 输出当前节点的值 console.log(currentNode.val); // 将currentNode节点指向next currentNode = currentNode.next; } while (currentNode)
得到依次输出结果：23、6、15
链表遍历的时间复杂度是O(n)O(n)O(n)，空间复杂度是O(1)O(1)O(1)
做好了准备就可以上菜了，哦不，小二，上题！
二、LeetCode 2. 两数之和
题目介绍：
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入： l1 = [2,4,3], l2 = [5,6,4] 输出： [7,0,8] 解释： 342 + 465 = 807.
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function(l1, l2) { // 待输入... }
三、解题思路
- 第一种解法：老实人的想法从给出的信息上，我们可以看出listNode都是逆序存储的整数，最终的是要将两个数进行累加，然后再逆序成ListNode的形式。可以分成两步来做：
- 将l1、l2转为整数，进行相加；
b. 将相加的和，以ListNode形式进行逆序存储
/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function(l1, l2) { // 声明字符串变量 num1、num2 let num1 = ''; let num2 = ''; // 将链表l1遍历，转为整数字符串 while (l1) { num1 = l1.val + num1; // 移动指针 l1 = l1.next; } // 同理 while (l2) { num2 = l2.val + num2; l2 = l2.next; } // 得出结果，并转为字符串 const num = (+num1 + +num2).toString(); const len = num.length; // 逆序存储，取num的最后一个元素 const headNode = new ListNode(num[len - 1]); // 将current指针指向headNode let current = headNode; // // 从倒数第二个字符开始 let i = len - 1 - 1; while (i >= 0) { // 获取下一个节点 const next = new ListNode(num[i]); // 使用next属性链接 current.next = next; // 移动current指针 current = next; // 移动索引 i--; } // 返回结果 return headNode; };
我们使用测试用例来 执行代码，似乎是没有什么问题。
OK，提交！看看效果！
没有通过所有的测试用例，这是为什么呢？！
我们来看下，此处的测试用例：
// 输入 [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1] [5,6,4]
为什么结果会是 [0,3,NaN,NaN,1]?
我们在代码中是将两个数相加得到整数结果，再使用toString()转成了字符串。 在JS中如果数值达到了科学计数法的量级，该碧昂量会使用科学计数法来表示，导致toString()转化时不是我们所想要的。
const a = 100; console.log(a); // 100 // 超大的一个值 const b = 10000000000000000000000000000000 console.log(b); // 1e+31 console.log(b.toString()); // "1e+31"
由此导致后续的计算出现了问题。
在这里给各位小伙伴，留个思考题：科学计数法如何转为正常的字符串展示呢？欢迎大家动手尝试下~
按照老实人的做法，我们满足了绝大多数的需求，还是并没有完全解决问题！ 需要换一个思路来考虑。
- 第二种解法：十进制内的加法
我们知道l1和l2都是listNode格式的链表，而且是逆序的。也就是说，l1、l2从前往后看可以依次视为个、十、百、千、万依次排列。
针对l1、l2在相同位置上，执行累加不就得到了最终目标结果该位置上的值了吗？在这里还要注意，十进制的特点：满十进一！
// 输入： [2, 4, 3] [5, 6, 4] // 输出 [7, 0, 8]
从这个思考点出发，我们重新梳理逻辑，考虑算法的实现：
var addTwoNumbers = function(l1, l2) { // 初始化头结点 const headNode = new ListNode(); let current = headNode; let addOne = 0; while (addOne || l1 || l2) { // 注意考虑l1、l2长度不一致以及最后一位要进一的问题，可能会导致进入循环时，l1、l2为null const num = addOne + (l1 ? l1.val : 0) + (l2 ? l2.val : 0); // 只保留num的个位数，十位数要进一 current.val = num % 10; // 判断是否要进1 addOne = num >= 10 ? 1 : 0; // 移动指针 l1 = l1 ? l1.next : null; l2 = l2 ? l2.next : null; // 判断是否有下一个节点 if (addOne || l1 || l2) { current.next = new ListNode(); current = current.next; } else { current.next = null } } return headNode; };
Congratulations!
四、总结
今天我们接触到了一种新的线性数据结构 链表，了解了其构造以及链表的遍历方式。
在LeetCode 2. 两数之和的问题上，从“老实人”算法到“十进制内的加法”算法，我们探寻了该算法中一种更优的解。
在“老实人”算法中，也注意到了数值类型中，在科学计数法量级上的变量，调用toString()时得到的结果是不同于我们常规的认识。
今天我们就到这里，期待明天与大家的相遇！
算法-从菜鸟开始，而无止境。与君共勉！
