前言

传说在公元1 世纪的犹太战争中，犹太历史学家弗拉维奥·约瑟夫斯和他的40 个同胞被罗马士兵包围。犹太士兵决定宁可自杀也不做俘虏，于是商量出了一个自杀方案。他们围成一个圈，从一个人开始，数到第三个人时将第三个人杀死，然后再数，直到杀光所有人。约瑟夫和另外一个人决定不参加这个疯狂的游戏，他们快速地计算出了两个位置，站在那里得以幸存。写一段程序将n 个人围成一圈，并且第m个人会被杀掉，计算一圈人中哪两个人最后会存活。使用循环链表解决该问题。

看到这个问题首先想到的是要用到循环链表，还有就是要计算链表中有多少个元素，这两点很重要。再有就是找到当前节点和在链表中向前移动m个节点。下面一一分析：循环链表很容易实现，就是初始化的时候使链表的头节点的下一个指向它自己，这样初始化一个空节点，注意链表的头不是节点。写法如下：this.head.next = this.head;计算链表中有多少个元素也很简单，只需要找到头节点，然后往下走直到再次回到头结点

代码如下：

var node = this.head;var i = 0;while (!(node.next.element == "head")){ node = node.next; i++;}return i;

在初始化链表的时候我们定义一个当前节点，将它赋值为头节点this.currentNode = this.head; ，这样在移动节点的时候就可以用它指向下一个节点。向前移动节点的时候有个地方需要注意，如果当前移动到头节点上需要再向前移动一个节点this.currentNode.next.next 。

代码如下：

while (n>0){ if(this.currentNode.next.element == "head"){ this.currentNode = this.currentNode.next.next; }else{ this.currentNode = this.currentNode.next; } n--;}

代码实现

/** * 使用循环链表实现解决约瑟夫环问题 * *///链表节点function Node(element){ this.element = element; this.next = null;}//定义链表类function LList(){ this.head = new Node("head"); this.head.next = this.head; this.find = find; this.insert = insert; this.findPrevious = findPrevious; this.remove = remove; this.currentNode = this.head; //从链表当前节点向前移动n个节点 this.advance = advance; //当前链表中有多少个元素 this.count = count; this.display = display;}//查找节点function find(item){ var currNode = this.head; while (currNode.element != item){ currNode = currNode.next; } return currNode;}//插入新节点function insert(newElement, item){ var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; current.next = newNode;}//查找当前节点的上一个节点function findPrevious(item){ var currNode = this.head; while (!(currNode.next == null) && (currNode.next.element != item)){ currNode = currNode.next; } return currNode;}//移除当前节点function remove(item){ var prevNode = this.findPrevious(item); if(!(prevNode.next == null)){ prevNode.next = prevNode.next.next; }}//向前移动n个节点function advance(n){ while (n>0){ if(this.currentNode.next.element == "head"){ this.currentNode = this.currentNode.next.next; }else{ this.currentNode = this.currentNode.next; } n--; }}//当前链表中有多少个元素function count(){ var node = this.head; var i = 0; while (!(node.next.element == "head")){ node = node.next; i++; } return i;}//输出所有节点function display(){ var currNode = this.head; while (!(currNode.next == null) && !(currNode.next.element == "head")){ document.write(currNode.next.element + "&nbsp;"); currNode = currNode.next; }}var person = new LList();person.insert('1','head');person.insert('2', '1');person.insert('3', '2');person.insert('4' , '3');person.insert('5' , '4');person.insert('6' , '5');person.insert('7' , '6');person.insert('8' , '7');person.insert('9' , '8');person.insert('10' , '9');person.display();document.write('<br>');var n = 3;while (person.count() > 2){ person.advance(n); person.remove(person.currentNode.element); person.display(); document.write('<br>');}

这里我们假设有10个人，每次数到第三个人的时候这个人自杀，最后输出的结果如下：

最后结果是约瑟夫和他的同伴一个站在队伍的第4个，一个站在队伍的第10个，最后只剩下他们两个人。不知道历史上有没有这件事，如果真的有这件事，在这么短的时间内解决这个问题，约瑟夫真他么是个天才，不知道当时他有没有用指针来解决这个问题，还是用普通的数组递归解决。

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流。