概念

链表是一种非连续的存储结构。
一个链表由若干节点构成，而节点间的联系是前一个节点“指向后一个节点”。如下图所示：
image.png

这种顺序结构，我们还有一种数据结构是数组，它们核心的不同就是：链表是不连续的存储空间，而数组是连续存储空间，这两种结构带来一些操作上的取舍：

  • 链表的访问某一条数据是非常慢的，如果我想访问最后一个节点的数据需要全部节点都遍历一遍，而数组只用下标就够了，直接能找到你需要访问的元素。
  • 但是链表的优势，在于增加、删除节点操作。链表需要增加和删除的时候，直接改变指针的指向即可。但是数组的话，可能牵扯移动周边元素的操作。

实现

JS中，没有原生的实现，不过我们实现起来也非常简单。

  1. // 定义节点
  2. interface ListNode {
  3.     data: any;
  4.   next: ListNode;
  5. }
  7. // 构造节点
  8. const a = {
  9.     data: 'a',
  10.   next: null,
  11. }
  13. const b = {
  14.     data: 'a',
  15.   next: null,
  16. }
  18. const c = {
  19.     data: 'a',
  20.   next: null,
  21. }
  23. a.next = b;
  24. b.next = c;

这里我们的一个简单链表就构造好了，构造了一个a -> b -> c的结构。
删除元素(假设删除b， a -> b -> c)：

  1. a.next = c;

增加元素，比如，a -> b -> c增加一个newNode，在b、c之间：

  1. b.next = newNode;
  2. newNode.next = c;

遍历链表的操作

  1. // 假设链表结构
  2. interface ListNode {
  3.     data: any;
  4.   next: ListNode;
  5. }
  7. // 假设存在一个链表 head
  8. // 如何遍历其每一个节点的数据
  9. // 下面是标准操作
  11. // 声明一个引用（或非严格可叫指针，但是js里面没有指针）
  12. // 指向链表头部
  13. let p = head;
  14. while(p) {
  15.   // 你希望的操作
  16.   // console.log(p.data);
  17.   p = p.next;
  18. }

JS中的原型链

JS的原型链是一个老生常谈的问题。原型链可以理解成是JS这种语言实现继承的方式（通常编程语言有class和原型两种方式实现继承）。
简单来说，JS中一个对象的instance被new出来了之后，它会有一个属性去指向自己的原型对象（也是类的构造函数的原型对象），而这个所谓“自己的原型对象”本质上也是一个对象，那么它也有所谓“自己的原型对象”，那么这个指向关系会继续下去，最终，我们这个指向旅程终点是Object这一级。
上面的概念在具体代码层面就是：

  1. 每一个类的构造函数都会关联一个原型对象。这个原型对象和类的构造函数的关联关系是这样建立的：类的构造函数通过属性prototype指向原型对象；原型对象通过属性constructor指回类的构造函数。可以看到构造函数和原型对象的关联是双向的。

  2. 类的instance（实例）会关联类的原型对象。当代码中A类被new了一个新的实例对象时，默认在这个对象中会有一个属性，通常是叫proto，这个属性的值指向其原型对象，此原型对象和上文提到的类构造函数的原型对象是同一个对象。

    基于这一点：假设 const ins = new ClassX()，那么我们就有：ins.proto === ClassX.prototype是true;
    这有什么用呢？在JS中，如果查找某个对象有什么属性，是顺着原型链向上找的，如果原型链上访问到的对象中存在这个属性，那么其值就是待查找的某个属性的值。
    另外一点，运算符instanceof也是通过原型链的关系来判断的。
    那么，让我们再从链表的角度再来看下原型链。
    从数据结构的角度来看，原型链就是一个链表结构，只不过，节点和节点间的关系不是next，而是proto，但是本质不都是一个指针或引用呗。
    那么，我们想向遍历链表那样遍历原型链该怎么做？

    1. let p = something;
    2. while(p){
    3. // ....
    4. p = p.__proto__
    5. }

    另外一个问题，如何实现下instanceof ？

    面试题

    类似instanceof运算符的instanceOf方法

    要求实现一个instanceOf()方法和instancof运算符的功能一致

    1. interface DefineInstanceOf: (objToVerify:Object, constructorToVerify:Function) => boolean

    很简单：

    1. const instanceOf: DefineInstanceOf = (objToVerify, constructorToVerify) => {
    2.  let p = objToVerify;
    3. while(p) {
    4.    if(p.__proto__ === constructorToVerify.prototype) {
    5.      return true;
    6.  }
    7.  p = p.__proto__;
    8. }
    9.  return false;
    10. }

    测试用例
    instanceOf({}, Object)
    true
    instanceOf(()=>{}, Object)
    true
    instanceOf(()=>{}, Array)
    false
    _

    拿到深层次对象的指定访问路径的值

    假设有个对象

    1. const obj = {
    2.  a: {
    3.    aa: {
    4.      aaa: {
    5.        aaaa: 'I Love This Game!'
    6.    }
    7.  }
    8. },
    10. b: {
    11.    bb: 22,
    12. }
    13. }

    比如我想拿到obj.a.aa.aaa.aaaa的值通常情况下

    1. // 一套optional访问就能搞定
    2. obj.a?.aa?.aaa?.aaaa

    但是这种嵌套关系，换一个角度理解，也是一种链式关系，那么我们从链表的角度去理解，模拟链表遍历的操作，可以写下面这个函数：

    1. const getAttrValueOptional = (object, attrs: string[]) =>{
    2. let p = object;
    3. while(p && attrs.length > 0){
    4.  p = p[attrs.shift()]
    5. }
    7. return p
    8. }

测试用例
getAttrValueOptional(obj, [‘a’, ‘aa’, ‘aaa’, ‘aaaa’])
“I Love This Game!”

_getAttrValueOptional(obj, [‘a’, ‘aa’, ‘aaa’, ‘b’])
undefined

_getAttrValueOptional(obj, [‘b’, ‘bb’])
22

_getAttrValueOptional(obj, [‘b’, ‘bb’, ‘c’])
undefined

_getAttrValueOptional(obj, [])
obj

LeetCode 237: 删除链表的节点

删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 — head = [4,5,1,9]，它可以表示为:

这个题目，给到你的是一个node，是想让你删除这个node。
很容易想到，那就是之前元素的next指向之后元素。但是很遗憾，在这个题里面拿不到。
但是我们换一个思路：“偷梁换柱”
把这个元素的数据域换成后一个元素的数据域。
把这个元素的next指针设置成后一个元素的next指针的值。

LeetCode 206: 反转链表

反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

前后两个指针遍历，改变next指针

LeetCode 2: 两数相加

两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

每一位相加，但是要注意求和产生的进位，以及遍历完链表之后还有没进位，如果有，还需要额外构造一个节点。

LeetCode 83: 删除链表的重复元素

删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3

很容易想到的一个思路就是在遍历每个节点的时候记录下节点的值，放到set里面，在如果某个节点的值是出现过的，就删除这个节点。
这个题简单就简单在他是一个排序链表，所以上面比较通用的判断出现过没有的方法就没必要了，因为排序的链表，如果有重复元素，那么重复元素肯定相邻。
这样，判断的条件就从set.has()变成node.val === node.next.val，节省了空间，空间复杂度从o(n)变成o(1)了。
还有一点需要注意的是，遍历的时候，不是每一次都有推进指针的，我们当遇到非重复节点的时候推荐，反之，不推进指针，这样，可以防止连续n个都是相同值元素。

LeetCode 141: 环形链表

环形链表

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
链表(Linked List) - 图2
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
链表(Linked List) - 图3
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

LeetCode的这个题目中的输入输出像是测试用例的输入输出，意思就是这么个意思，但是我们编程期间的输入输出不是这样，这个题真正的入参是一个head，出参是布尔值。
这个题目也可用遍历，每一个节点在set中放入next的值，然后校验set中的值是否出现过来完成

不过这个题有一个进阶挑战
进阶：
你能用 _O(1)（即，常量）内存解决此问题吗？

我们上述思路引入了set，空间复杂度是O(n)
完成这个进阶挑战，需要一个思路叫，快慢双指针。
两个步进不同的指针，如果有环，肯定能遇见的。

  1. var hasCycle = function(head) {
  3.     // 使用set 判断
  4.     // let p = head;
  5.     // const pointerSet = new Set();
  6.     // while(p && p.next){
  7.     //     if(pointerSet.has(p)) {
  8.     //         return true
  9.     //     }
  11.     //     pointerSet.add(p);
  12.     //     p = p.next;
  13.     // }
  14.     // return false;
  16.     // 进阶：
  17.     // 你能用 O(1)（即，常量）内存解决此问题吗？
  19.     // 快慢双指针
  20.     let fast = head;
  21.     let slow = head;
  23.     while(fast && fast.next && fast.next.next && slow && slow.next) {
  24.         fast = fast.next.next;
  25.         slow = slow.next;
  27.         if(fast === slow){
  28.             return true;
  29.         }
  30.     }
  31.     return false
  33. };