javascript循环链表之约瑟夫环的实现方法

当我们在处理需要循环的数据时，循环链表是一种非常常见的数据结构。而约瑟夫环是一个经典的可用于解决Josephus问题的算法，即在一个有限的环中每隔k个（k > 1）数杀掉一个人，直到剩下最后一个人。在 JavaScript 中，我们可以用循环链表来实现该算法。

首先，我们需要定义一个循环链表数据结构

循环链表由链表头和尾组成，头尾相接即为循环链表。我们需要实现添加元素、删除元素、获取某个元素等基本操作。以下是一个简单的 JavaScript 循环链表实现：

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class CircularLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // 添加元素
  append(value) {
    const newNode = new Node(value);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
      newNode.next = this.head;
    }
    this.length++;
  }

  // 删除元素
  remove(position) {
    if (position > -1 && position < this.length) {
      let current = this.head;
      let previous = null;
      let index = 0;
      if (position === 0) {
        this.head = current.next;
        this.tail.next = this.head;
        if (this.length === 1) {
          this.tail = null;
        }
      } else if (position === this.length - 1) {
        current = this.tail;
        previous = this.head;
        while (previous.next !== this.tail) {
          previous = previous.next;
        }
        this.tail = previous;
        this.tail.next = this.head;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      this.length--;
    }
  }

  // 获取某个元素
  getElementAt(index) {
    if (index >= 0 && index < this.length) {
      let node = this.head;
      for (let i = 0; i < index && node !== null; i++) {
        node = node.next;
      }
      return node;
    }
    return null;
  }

  // 辅助函数：打印循环链表
  print() {
    let current = this.head;
    let str = "";
    let index = 0;
    while (index < this.length) {
      str += current.value + " ";
      current = current.next;
      index++;
    }
    console.log(str);
  }
}

接下来，我们来实现约瑟夫环算法

约瑟夫环的算法思路如下：

1. 创建一个长度为n的循环链表
2. 从链表头开始依次遍历链表，每遍历到第k个节点，就将该节点删除
3. 不断重复步骤2，直到只剩下一个节点为止

接下来，我们按照算法思路，来实现约瑟夫环的代码：

function josephus(n, k) {
  const list = new CircularLinkedList();
  for (let i = 1; i <= n; i++) {
    list.append(i);
  }
  let current = list.head;
  while (list.length > 1) {
    let count = 1;
    while (count < k) {
      current = current.next;
      count++;
    }
    const next = current.next;
    list.remove(list.indexOf(current.value));
    current = next;
  }
  return list.head.value;
}

我们调用 josephus(10, 2)，即可得到结果为 5，即当有10个人，每隔2个人杀掉一个，最后剩下的人的编号为5。

示例2：将删除过程输出，供参考

为了更好地理解算法的实现过程，我们可以将删除过程输出。这里将算法修改一下，增加输出功能：

function josephusWithLog(n, k) {
  const list = new CircularLinkedList();
  for (let i = 1; i <= n; i++) {
    list.append(i);
  }
  let current = list.head;
  let log = "";
  while (list.length > 1) {
    let count = 1;
    while (count < k) {
      current = current.next;
      count++;
    }
    const next = current.next;
    const removed = list.remove(list.indexOf(current.value));
    log += `第${current.value}号被删除，`;
    if (removed !== null) {
      log += `剩余人数为${list.length}，剩余人员为：`;
      let current = list.head;
      while (current !== null) {
        log += current.value + " ";
        current = current.next;
      }
      log += "\n";
    }
    current = next;
  }
  log += `最后剩余${list.head.value}号。`;
  console.log(log);
  return list.head.value;
}

我们调用 josephusWithLog(10, 2)，即可得到下面的输出：

第2号被删除，剩余人数为9，剩余人员为：1 3 4 5 6 7 8 9 10 
第4号被删除，剩余人数为8，剩余人员为：1 3 5 6 7 8 9 10 
第6号被删除，剩余人数为7，剩余人员为：1 3 5 7 8 9 10 
第8号被删除，剩余人数为6，剩余人员为：1 3 5 7 9 10 
第10号被删除，剩余人数为5，剩余人员为：1 3 5 7 9 
第5号被删除，剩余人数为4，剩余人员为：1 3 7 9 
第1号被删除，剩余人数为3，剩余人员为：3 7 9 
第9号被删除，剩余人数为2，剩余人员为：3 7 
最后剩余3号。

从输出可以清晰地看到，当有10个人，每隔2个人杀掉一个，算法的具体执行过程。