单链表，循环链表，双向链表

实现单链表

class LList {
  constructor() {
    this.head = new ListNode("head");
  }
  find(val) {
    // 寻找节点
    let currNode = this.head;
    while (currNode && currNode.val !== val) {
      currNode = currNode.next;
    }
    return currNode;
  }
  add(val) {
    // 在链表尾部增加节点
    let currNode = this.head;
    const newNode = new ListNode(val);
    while (currNode.next !== null) {
      currNode = currNode.next;
    }
    currNode.next = newNode;
  }
  insert(val, preVal) {
    // 插入节点，先寻找要插入的节点，再在节点后面插入节点，节点可能不存在，不存在则在链表尾部插入节点
    let currNode = this.head;
    const newNode = new ListNode(val);
    while (currNode.next && currNode.val !== preVal) {
      currNode = currNode.next;
    }
    currNode.next = newNode;
  }
  remove(val) {
    // 寻找到被删除节点的前驱节点，然后连接其后继节点
    let currNode = this.head;
    while (currNode.next) {
      if (currNode.next.val === val) {
        currNode.next = currNode.next.next; // 前驱节点连接其后继节点的后继节点
        break;
      }
      currNode = currNode.next;
    }
    console.log("没找着");
  }
  display() {
    // 逐个打印节点
    if (this.head.next === null) {
      console.log("空的");
      return;
    }
    let currNode = this.head.next;
    while (currNode !== null) {
      console.log(currNode.val);
      currNode = currNode.next;
    }
  }
}
function ListNode(val) {
  // 生成节点
  this.val = val;
  this.next = null;
}

实现循环链表

class CSLList {
  constructor() {
    this.first = null;
  }
  insert(name, no) {
    if (this.first === null) {
      // 第一个节点的后继指向自己
      this.first = new Node(name, no);
      this.first.next = this.first;
    } else {
      let newNode = new Node(name, no);
      let flag = false; //通过这个标志判断是不是存在这个编号
      let currNode = this.first;
      let preNode = this.first
      while (true) {
        if (preNode.no < newNode.no &&currNode.next.no > newNode.no) break; // 找到插入数据的位置
        if (currNode.no > currNode.next.no && currNode.no < newNode.no) break; // 已经遍历到最大数字的位置，并且最大数字比插入的数字小，所以插入最后
        if (currNode.next.no === newNode.no) {
          flag = true;
          break;
        } //有重复编号的数据存在
        preNode = currNode
        currNode = currNode.next;
      }
      if (flag) {
        console.log("已存在相同编号数据");
      } else {
        newNode.next = currNode.next;
        currNode.next = newNode;
      }
    }
  }
  remove(countNo) {
    if (this.first === null) {
      console.log("空的");
      return null;
    }
    if (this.first.next === this.first) {
      console.log("移除了" + this.first.no + this.first.name);
      this.first = null;
      return null;
    }
    if (!countNo || countNo < 1) {
      console.log("入参错误");
      return null;
    }
    for (let i = 0; i < countNo - 1; i++) {
      // 向后移动countNo - 1个位置，然后删除该位置元素
      this.getNext();
    }
    let temp = this.first.next;
    this.first.next = this.first.next.next;
    console.log("移除了" + temp.no + temp.name);
    return temp.no;
  }
  getNext() {
    // 往后移动一位
    if (this.first === null) {
      console.log("空的");
      return;
    }
    this.first = this.first.next;
  }
  length() {
    if (this.first === null) {
      return 0;
    }
    let count = 1;
    let temp = this.first;
    while (temp.next !== this.first) {
      // 累加到找到自身
      count++;
      temp = temp.next;
    }
    return count;
  }
  display() {
    if (this.first === null) {
      console.log("空的");
      return;
    }
    let temp = this.first;
    while (temp.next !== this.first) {
      // 依次打印节点信息
      console.log(temp.no + temp.name);
      temp = temp.next;
    }
  }
}
function ListNode(val, no) {
  // 生成节点
  this.val = val;
  this.no = no;
  this.next = null;
}

用循环链表实现约瑟夫问题

class CSLList {
  constructor() {
    this.first = null;
  }
  insert(name, no) {
    if (this.first === null) {
      // 第一个节点的后继指向自己
      this.first = new ListNode(name, no);
      this.first.next = this.first;
    } else {
      let newNode = new ListNode(name, no);
      let flag = false; //通过这个标志判断是不是存在这个编号
      let currNode = this.first;
      if (currNode.next !== currNode) { // 当节点数大于1时
        while (true) {
          if (currNode.next.no > newNode.no) break; // 找到插入数据的位置
          if (currNode.no > currNode.next.no) break; // 已经遍历到最大数字的位置，所以插入到此位置
          if (currNode.next.no === newNode.no) {
            flag = true;
            break;
          } //有重复编号的数据存在
          currNode = currNode.next;
        }
      }
      if (flag) {
        console.log("已存在相同编号数据");
      } else {
        newNode.next = currNode.next;
        currNode.next = newNode;
      }
    }
  }
  remove(countNo) {
    if (this.first === null) {
      console.log("空的");
      return null;
    }
    if (this.first.next === this.first) {
      console.log("移除了" + this.first.no + this.first.name);
      this.first = null;
      return null;
    }
    if (!countNo || countNo < 1) {
      console.log("入参错误");
      return null;
    }
    for (let i = 0; i < countNo - 1; i++) {
      // 向后移动countNo - 1个位置，然后删除该位置元素
      this.getNext();
    }
    let temp = this.first.next;
    this.first.next = this.first.next.next;
    console.log("移除了" + temp.no + temp.name);
    return temp.no;
  }
  getNext() {
    // 往后移动一位
    if (this.first === null) {
      console.log("空的");
      return;
    }
    this.first = this.first.next;
  }
  length() {
    if (this.first === null) {
      return 0;
    }
    let count = 1;
    let temp = this.first;
    while (temp.next !== this.first) {
      // 累加到找到自身
      count++;
      temp = temp.next;
    }
    return count;
  }
  display() {
    if (this.first === null) {
      console.log("空的");
      return;
    }
    let temp = this.first;
    while (temp.next !== this.first) {
      // 依次打印节点信息
      console.log(temp.no + temp.name);
      temp = temp.next;
    }
  }
}
function ListNode(val, no) {
  // 生成节点
  this.name = val;
  this.no = no;
  this.next = null;
}
function Joseph() {
  let llist = new CSLList();
  for (let i = 0; i < 20; i++) {
    llist.insert("小孩" + (i + 1), i + 1);
  }
  let countNo = 5;
  while (llist.remove(countNo) !== null) {}
}
Joseph();