什么是链表？

链表

原文链接：https://note.noxussj.top/?source=sifo

链表是有序的数据结构，链表中的每个部分称为节点。可以首、尾、中间进行数据存取，链表的元素在内存中不必是连续的空间，每个节点通过 next 指针指向下一个节点。

优点

链表的添加和删除不会导致其余元素位移。

缺点

无法根据索引快速定位元素。

数组和链表区别

获取、修改元素时，数组效率高
添加、删除元素时，链表效率高
数组添加、移除会导致后续元素位移，性能开销大

环形链表

指的是链表最后一个节点的 next 指向第一个节点，形成首尾相连的循环结构。

链表环路检测

解题思路

快慢指针法实现
slow 指针每次移动一位，fast 指针每次移动两位，如果他们相遇则说明链表存在环
新指针 ptr 从 head 开始移动，与 slow 相遇的位置即为环的起点
由 fast 指针移动距离为 slow 的两倍可得出公式： a + (nb + nc + b) = 2(a + b)
变化处理后得到新公式： a = (n – 1)(b + c) + c

实现功能

在 JavaScript 中没有链表，我们可以通过模拟一个类或者是通过 Object 实现链表的所有功能。

节点类

value 当前节点值
next 指向下一个节点

链表类
addAtTail 尾部添加节点
addAtHead 头部添加节点
addAtIndex () 指定位置添加节点
get 获取节点
removeAtIndex () 删除指定节点

应用场景

leetcode 两数相加

基础案例

通过对象实现

    // 链表
    let a = { val: 'a', next: null }
    let b = { val: 'b', next: null }
    let c = { val: 'c', next: null }
    let d = { val: 'd', next: null }
    
    a.next = b
    b.next = c
    c.next = d
    
    // 尾部添加节点
    let e = { val: 'e', next: null }
    d.next = e
    
    // 头部添加节点
    let z = { val: 'z', next: null }
    z.next = a
    a = z
    
    // 指定位置添加节点
    let f = { val: 'f', next: null }
    c.next = f
    f.next = d
    
    // 删除指定节点
    d.next = null

通过类模拟实现

    /**
    * 节点类
    */
    class Node {
    constructor(value) {
    this.value = value
    this.next = null
    }
    }
    
    /**
    * 链表类
    */
    class Link {
    constructor() {
    this.head = null
    this.count = 0
    }
    
    /**
    * 尾部添加节点
    */
    addAtTail(item) {
    if (this.count === 0) {
    this.head = new Node(item)
    
    this.count++
    
    return this.head
    }
    
    let endNode = this.head
    
    while (endNode.next) {
    endNode = endNode.next
    }
    
    endNode.next = new Node(item)
    
    this.count++
    
    return item
    }
    
    /**
    * 头部添加节点
    */
    addAtHead(item) {
    if (this.head) {
    const oldHead = this.head
    
    this.head = new Node(item)
    this.head.next = oldHead
    } else {
    this.head = new Node(item)
    }
    
    this.count++
    
    return item
    }
    
    /**
    * 指定位置添加节点
    */
    addAtIndex(index, item) {
    if (this.isInvalidIndex(index) || !this.head) {
    return -1
    }
    
    if (index === 0) {
    this.addAtHead(item)
    
    return item
    }
    
    let prev = this.head
    
    while (index > 0) {
    index--
    }
    
    const next = prev.next
    
    const cur = new Node(item)
    
    prev.next = cur
    cur.next = next
    
    this.count++
    
    return item
    }
    
    /**
    * 获取节点
    */
    get(index) {
    if (this.isInvalidIndex(index) || !this.head) {
    return -1
    }
    
    let cur = this.head
    
    while (index > 0) {
    cur = cur.next
    
    index--
    }
    
    return cur
    }
    
    /**
    * 删除指定节点
    */
    removeAtIndex(index) {
    if (this.isInvalidIndex(index) || !this.head) {
    return -1
    }
    
    if (index === 0) {
    const oldHead = this.head
    this.head = this.head.next
    
    this.count--
    
    return oldHead
    }
    
    let prev = this.head
    
    while (index - 1 > 0) {
    prev = prev.next
    
    index--
    }
    
    const cur = prev.next
    
    prev.next = cur.next
    
    this.count--
    
    return cur
    }
    
    /**
    * 判断index是否为空，是否超出数据长度大小
    */
    isInvalidIndex(index) {
    if (index === '' || index === null || index === undefined || index  this.count - 1) {
      return true
      }
    
      return false
      }
      }
    
      const link = new Link()
    
      link.addAtTail('a')
      link.addAtTail('b')
      link.addAtTail('c')