1. 介绍

链表是有序的列表，但是它在内存中是无序的, 链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

img

2. 单向链表

class Node {
  constructor(value) {
    this.value = value
    this.next = null
  }
}
class LinkList {
  constructor() {
    this.size = 0
    this.head = new Node(null)
    this.head.next = null
  }
  checkIndex(index){
    if (index < 0 || index > this.size) {
      throw new Error('位置错误')
    }
  }
  find(pre, index, curIndex) {
    if (index === curIndex) {
      return pre
    }
    return this.find(pre.next, index, curIndex+1)
  }
  add(value, index) {
    this.checkIndex(index)
    let pre = this.find(this.head, index, 0)
    let newNode =  new Node(value)
    newNode.next = pre.next
    pre.next = newNode
    this.size++
    return this.size
  }
  remove(index) {
    this.checkIndex(index)
    let pre = this.find(this.head, index, 0)
    let delNode = pre.next
    pre.next = delNode.next
    this.size--
    return this.size
  }
  show() {
    let tem = this.head.next
    while(tem !== null){
      console.log('this'+tem.value);
      tem = tem.next
    }
  }
}
let test = new LinkList()
test.add(1,0)
test.add(2,1)
test.add(3,2)
console.log(test.size);
// test.remove(2)
console.log(test.show());

3. 约瑟夫问题

问题描述

Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

思路

用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

实现

class Node {
  constructor(v) {
    this.value = v
    this.next = null
  }
}
class LinkList {
  constructor() {
    this.firstNode = new Node(null)
    this.curNode = this.firstNode
  }
  add(num) {
    for (let i = 1; i <= num; i++) {
      let newNode = new Node(i)
      this.curNode.next = newNode
      newNode.next = this.firstNode.next
      this.curNode = newNode
    }
  }
  show() {
    let tem = this.firstNode.next
    while (true) {
      console.log(tem.value);
      if (tem === this.curNode) {
        break
      }
      tem = tem.next
    }
  }
  josephu(startIndex, count, nums) {
    if (this.firstNode.next === null || startIndex < 1 || startIndex >= nums) {
      console.log("参数错误");
      return
    }
    let tem = this.firstNode.next
    let helper = this.curNode
    for (let i = 0; i < startIndex - 1; i++) {
      tem = tem.next
      helper = helper.next
    }

    while (true) {
      if (tem == helper) {

        break;
      }
      for (let i = 0; i < count - 1; i++) {
        tem = tem.next
        helper = helper.next
      }
      console.log(tem.value + '出去');
      tem = tem.next
      helper.next = tem
    }
    console.log(tem.value + '出去');
  }
}
let test = new LinkList()
test.add(25)
test.josephu(1, 2, 25)