1.链表常用操作

const a = { val: 'a' };
const b = { val: 'b' };
const c = { val: 'c' };
const d = { val: 'd' };
a.next = b;
b.next = c;
c.next = d;
// 遍历链表
let p = a;
while (p) {
    console.log(p.val);
    p = p.next;
}
// 插入
const e = { val: 'e' };
c.next = e;
e.next = d;
// 删除
c.next = d;

2.原型链与链表

原型链的本质是链表
原型链上的节点是各种原型对象，比如Function.prototype，Object.prototype…
原型链通过proto属性链接各种原型对象
如果A沿着原型链能找到B.prototype，那么A instanceof B为true
如果A沿着原型链没有找到X属性，那么会沿着原型链找X属性
3.使用链表指针获取JSON的节点
```javascript const json = { a: {
```
  b: {
      c: 1
  }
```
}, d: {
```
  e: 2
```
} } const path = [‘a’, ‘b’, ‘c’]

let p = json path.forEach(k => { p = p[k] })

<a name="NOxWC"></a>
# 题目
<a name="uhiVd"></a>
## 1.删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例 1：
输入：head = [4,5,1,9], node = 5<br />输出：[4,1,9]<br />解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.<br />示例 2：
输入：head = [4,5,1,9], node = 1<br />输出：[4,5,9]<br />解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
提示：
链表至少包含两个节点。<br />链表中所有节点的值都是唯一的。<br />给定的节点为非末尾节点并且一定是链表中的一个有效节点。<br />不要从你的函数中返回任何结果。
```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
      // 将被删除元素的val赋值为下个元素的val
    node.val = node.next.val
      // 删除下个元素
      // 将下个元素的指针指向下下个元素
    node.next = node.next.next
};

2.反转链表

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

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
      // 双指针遍历
      // (1)p1 = {val: 1, next:{val: 2, next: {val: 3, next:{val: 4: next: {val: 5, next: null}}}}}
      // (2)p1 = {val: 2, next: {val: 3, next:{val: 4: next: {val: 5, next: null}}}}
    let p1 = head
    // (1)p2 = null
    // (2)p2 = {val: 1, next: null}
    let p2 = null
    while(p1) { 
          // (1)定义变量存储下个节点的元素,即{val: 2, next: {val: 3, next:{val: 4: next: {val: 5, next: null}}}}
        // (2)定义变量存储下个节点的元素,即{val: 3, next: {val: 4, next:{val: 5: next: null}}}}
          const tmp = p1.next
        // (1)让p1的next指向为p2(空), 即p1={val: 1, next: null}
        // (2)让p1的next指向为p2,即p1={val: 2, next: {val: 1, next: null}}
        p1.next = p2
          // (1)让p2赋值为 p1 即p2={val: 1, next: null}
          // (2)让p2赋值为 p1 即p2={val: 2, next: {val: 1, next: null}}
        p2 = p1
          // (1)让p1变成tmp p1={val: 2, next: {val: 3, next:{val: 4: next: {val: 5, next: null}}}}
          // (2)让p1变成tmp p1={val: 3, next: {val: 4, next:{val: 5: next: null}}}}
        p1 = tmp
    }
      // 返回p2
    return p2
};

3.两数相加

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

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

你可以假设除了数字 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]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

/**
 * 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) {
      // 创建一个链表
    const l3 = new ListNode(0)
    // 创建执政
    let p1 = l1
    let p2 = l2
    let p3 = l3
    // 定义十位上的进位值
    let carry = 0
    // 遍历链表
    while(p1 || p2) {
          // 取到遍历过程中的值
        const v1 = p1 ? p1.val : 0
        const v2 = p2 ? p2.val : 0
        // 算出来链表的个位相加结果
        const val = v1 + v2 + carry
        // 如果相加结果大于0
        // 就把十位数上的进位值赋值给carry
        carry = Math.floor(val / 10)
          // 给定义的新链表的next赋值一个新的链表
        p3.next = new ListNode(val % 10)
          // 处理两个链表不一样长的情况
          // 如果有值就准备遍历链表的下一个next
        if(p1) p1 = p1.next
        if(p2) p2 = p2.next
          // 指针指向新链表的下一位
        p3 = p3.next
    }
      // 处理新链表最后一位大于10的情况
      // carry有值就说明需要给新链表的next重新赋值一个新的链表
    if(carry) p3.next = new ListNode(carry)
      // 返回新链表的next
    return l3.next

};

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

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:
输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

思路：

链表是有序的，所以重复元素一定相邻
遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    let p = head
    // 遍历链表，
    // 但是会出现链表的最后一个元素的next为null，p.next.val会出错
    while(p && p.next) {
          // 如果发现当前元素和下个元素值相同，就删除下个元素
        if(p.val === p.next.val) {
            p.next = p.next.next
        } else {
              // [1,1,1]
              // 如果发现当前元素和下个元素值相同，就不移动指针，直接删除下个元素
            p = p.next
        }

    }
      // 返回头部就行
    return head

};

5.环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

进阶：
你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

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

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个有效索引。

思路：

两个人在圆形操场上起点同时起跑，速度快的人会超过速度慢的人一圈
用一快一慢两个指针遍历链表，如果指针相逢，那么链表就有圈，返回true
遍历结束后，还没有相逢就返回false

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
      // 定义两个指针
    let p1 = head
    let p2 = head
    // 有环的话，最后一个指针的next指向别的链表元素
    while(p1 && p2 && p2.next) {
          // 一块一慢
        p1 = p1.next
        p2 = p2.next.next
          // 相遇则有环
        if(p1 === p2) {
            return true
        }
    }
    return false

};

6.instanceof的原理，并用代码实现

如果A沿着原型链能找到B.prototype，那么A instanceof B为true
解法：遍历A的原型链，如果能找到B.prototype，返回true，否则返回false ```javascript const instanceOf = (A, B) => { let p = A while (p) {
```
    // 遍历A的原型链，如果能找到B.prototype，返回true
  if (p === B.prototype) {
      return true
  }
    // 移动指针
  p = p.__proto__
```
} return false } console.log(instanceOf([], Array));

```

7.场景题

foo.a - value a
foo.b - undefined
F.a - value a
F.b - value b

链表