链表

链表是一个**「线性」**结构，充分利用了计算机的内存空间，实现了灵活的内存状态管理。

链表：（链表由一系列节点（链表中每一个元素称为节点）组成，结点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据，另一个是存储指向下一个节点地址的指针）

单向链表 : 线性的数据结构

头指针：指向第一个节点的指针

头指针的意义在于：

可以确定第一个元素对应的存储位置

在访问链表时，总要知道链表存储在什么位置（从何处开始访问），由于链表的特性（next指针），知道了头指针，那么整个链表的元素都能够被访问，也就是说头指针是必须存在的

双向链表：下一个节点也可以指向上一个节点，互相指向,其实是在单向链表前面加了一个prev的指针，指向链表的前一个元素

单向循环链表：特点：尾指针指向头指针

双向循环链表

环形链表：任意两个节点之间存在闭环的话，都是环形链表

只需要判断链表是否有环。当链表没有环时是很好判断的，让一个指针一直往后走，遇见null了自然就没有环

由一系列节点组成，链表的数据是以节点来表示的，每个节点的构成：元素 + 指针（指向下一个节点地址的指针）

实现单向链表

js
//链表的节点数据结构
class Node {
  constructor(payload, next) {
    this.payload = payload; //存储当前元素的数据
    this.next = next; //指向下一个节点的地址指针
  }
}
//单向链表的类
class LikedList {
  constructor() {
    //头指针： 指向第一个节点的指针
    this.head = null; //头指针，默认指向null
    this.size = 0; //链表的长度，空链表默认是0
  }
  //向链表追加数据
  append(node) {
    let newNode = new Node(node);
    if (this.head === null) {
      this.head = newNode;
    } else {
      //获取最后一个节点
      let current = this.getNode(this.size - 1);
      //由于是追加，因此最后一个节点的next指向新的数据
      current.next = newNode;
    }
    this.size++;
  }
  //指定位置插入
  insert(index, node) {
    //如果插入的位置等于size,就是在最后的元素插入
    //处理边界条件
    if (index < 0 || index > this.size) {
      throw new Error('index out range');
    }
    let newNode = new Node(node);
    if (index === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      //获取前一个节点
      let pre = this.getNode(index - 1);
      newNode.next = pre.next;
      pre.next = newNode;
      this.size++;
    }
  }
  //删除位置指定的元素
  remove(index) {
    this.checkIndex(index);
    let current = this.head;
    if (index === 0) {
      this.head = current.next;
    } else {
      let pre = this.getNode(index - 1);
      current = pre.next;
      pre.next = current.next;
    }
    this.size--;
  }
  //查找指定的元素的索引
  indexOf(node) {
    let current = this.head;
    let index = 0;

    //查找，只要current不指向null就一直循环
    while (current.next) {
      if (current.payload === node) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }
  //查找
  find(head, index, currentIndex) {
    //如果是查找当前第一个节点，则返回head，因为head指向第一个节点
    if (index === currentIndex) return head;
    //通过next指针递归查找元素
    return this.find(head.next, index, currentIndex + 1);
  }
  // 获取单链表的最后一个节点
  findLast() {
    let currNode = this.head;
    while (currNode.next) {
      currNode = currNode.next;
    }
    return currNode;
  }
  // 检查index合法
  checkIndex(index) {
    if (index < 0 || index >= this.size) throw Error('index out range');
  }
  // 根据索引获取节点
  getNode(index) {
    this.checkIndex(index);
    return this.find(this.head, index, 0);
  }
}

const node = new LikedList();
node.append('aaa');
node.append('bbb');
node.append('ccc');
node.insert(1, 'ddd'); //aaa->ddd->bbb->ccc
console.log(node.indexOf('aaa')); //0
console.dir(node, { depth: 100 });

链表如何找到中间节点?

要找到链表的中间节点，可以使用“快慢指针”算法。具体步骤如下：

利用快慢指针思想，快指针每次走两步，慢指针走一步。当快指针走到底的时候，慢指针指向的就是链表的中间节点。需要注意的是，当链表长度为偶数位的时候，则慢指针指向的是中间偏右的节点，奇数的时候，指向的是中间节点

定义两个指针，一个称为“慢指针”，一个称为“快指针”，都从链表的头部开始遍历。
每次移动慢指针一个节点，快指针移动两个节点。
当快指针到达链表末尾时，慢指针所在的节点就是链表的中间节点。

javascript
function findMiddleNode(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

在这个函数中，head是链表的头节点。在while循环中，快指针每次移动两个节点，直到快指针到达链表末尾或下一个节点为null。每次循环中，慢指针都会移动一个节点。当快指针到达链表末尾时，慢指针所在的节点就是链表的中间节点。

实现单向链表​

链表如何找到中间节点?​

实现单向链表

链表如何找到中间节点?