链表

链表

数组：增加或者删除非首尾元素时，需要移动元素

链表：增加或者删除非首尾元素时，不需要移动元素，只需要修改其next的指向即可

注： JavaScript 没有链表结构，所以我们需要用Object来模拟链表

题目 删除链表中的节点

https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

时间复杂度：O(1)

空间复杂度：O(1)

/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function (node) {
  node.val = node.next.val // 将自己变成别人
  node.next = node.next.next // 干掉别人，达到自己消失的目的
};

题目 反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

时间复杂度：O(n)

空间复杂度：O(1) // p2里面都是p1的，所以不是新内存，temp因为是单个值，不是数组与矩阵，所以是O(1)

思路：每次循环的时候首先保存之后的链表，再讲当前链表指向新的链表，最后循环”之后的链表“，进而实现

[1,2,3,4,5] => []
[2,3,4,5] => [1]
[3,4,5] => [1,2]
[4,5] => [1,2,3]
[5] => [1,2,3,4]
[] => [1,2,3,4,5]

写法1 双指针

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let p1 = head // 链表
  let p2 = null
  while (p1) {
    const temp = p1.next // 首先保存当前的下一个指针 
    p1.next = p2 // 将当前指针指向新链表
    p2 = p1 // 替换之前的链表 [] => [1] => [2,1] => [3,2,1]
    p1 = temp // 为了下次循环,将下一个链表给p1(本次循环的已经被弹出) [1,2,3] => [2,3] => [3]
  }
  return p2 // 返回反转后的链表
};

写法2 递归

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  // 递归写法
  return reverse(null, head)

};

function reverse(now, old) {
  if (!old) { // 老数据没了,递归反转完成
    return now
  }
  let temp = old.next // 首先保存链表(除了自己)
  old.next = now // 将当前指针指向新链表
  return reverse(old, temp) // 将2个链表再执行一遍
}

题目 两数相加

https://leetcode-cn.com/problems/add-two-numbers/

时间复杂度：O(n)

空间复杂度：O(n)

思路：同时循环两个链表，在将数据放入一个新的链表中，对十位数需要进行额外的处理

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  let all = new ListNode(0) // 新建空链表
  let three = all  // 向新链表追加元素是需要指针,直接用all,链表头就没了
  let carry = 0 // 记录超出的十位数
  while (l1 || l2) { // 同时循环2个链表
    let val = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry // 同位数相加,并且加上上一位的超出的十位数
    carry = Math.floor(val / 10) // 获取超出的十位数
    three.next = new ListNode(val % 10) // 记录当前的余数
    three = three.next // 指向下一个链表
    if (l1) { // 2个链表长度不一致,需要判断
      l1 = l1.next
    }
    if (l2) {
      l2 = l2.next
    }
  }
  // 最后一位可能存在余数
  if (carry) {
    three.next = new ListNode(carry)
    three = three.next
  }
  return all.next
};

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

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

时间复杂度：O(n)

空间复杂度：O(1)

思路：遇到同样的，删除自己，没遇到，指针向后一位

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
  let all = head // 当前指针
  while (all && all.next) {
    if (all.val == all.next.val) {
      // 和下个一个节点一致,删除本阶段
      all.next = all.next.next
    } else {
      // 没有重复的,指针到下一个
      all = all.next
    }
  }
  return head
}

题目 环形链表

https://leetcode-cn.com/problems/linked-list-cycle/

题目解析: 给定一个特殊的链表，链表的最后一位再次指向链表中的某一个，这样会形成一个环，pos参数是未知的，通过算法判断该链表是否有环

写法1 特殊值法

时间复杂度:O(n)

空间复杂度：O(1)

特殊值一定要保证不能在链表中出现

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {

  	let all = head;
    while(all) {
      // 定一个特殊值，将遇到的每一项都变成这个特殊值
      //	如果有遇到了，就说明是存在环
      if(all.val == '123456789') {
        all = null
        return true
      } else {
        all.val = '123456789'
        all = all.next
      }
     
    }
  // 如果一次都没遇到这说明没有环
    return false
};

写法2 快慢指针

1. 为什么快指针与慢指针一定会相遇?

   一旦快指针进入环中，每次都离慢指针进一步，因为到了追上的时候，要么相隔1步，下一步相遇，要么相隔2步，下下次一定相遇

2. 快指针与慢指针相遇的时候，慢指针是否绕环超过了一圈

   不会，假设环长为N，环外长度为n，N一定大于n；并且根据第一题可知每次快指针都距离慢指针进一步，所以N与n最终会距离n，所以N>n

时间复杂度:O(n)

空间复杂度：O(1)

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
  let p1 = head
  let p2 = head
  while(p1 && p2 && p2.next) {
    p1 = p1.next
    p2 = p2.next.next
    if(p1 === p2) {
      return true
    }
  }
  return false
};

JavaScript原型链

obj -> Object.prototype -> null // 对象
func -> Function.prototype -> Object.prototype -> null // 方法
arr -> Array.prototype -> Object.prototype -> null // 数组

如果A沿着原型链能找到B.protype，那么 A instanceof B一定为true

如果A对象上面没有找到X属性，那么就会沿着原型链找到X属性

例如：Object.prototype.x = ‘x’,那么函数func.x也会为x,因为Function.prototype指向Object.prototype

instanceof如何实现？（遍历原型链）

遍历链表，寻找是否存在一致的

function instanceOf(params, type) {
  let p = params
  while (p) {
    if (p === type.prototype) {
      return true
    }
    p = p.__proto__
  }
  return false
}

应用 使用链表获取json的值

在知道全部键的情况下，或者说知道json中数据的的某个值，可以使用链表，嵌套for过于暴力

const json = {
  a: {
    b: {
      c: 1
    }
  }
}
const path = ['a', 'b', 'c']

let p = json
path.map(e => {
  p = p[e]
})

console.log(p);

总结

• 链表中的元素不是连续的，而是通过next指针连接的
• JavaScript没有链表，但是Object可有模拟链表
• 常用操作：遍历链表，修改链表next
• JavaScript的原型链也是链表，使用__proto__进行连接