大体思路是使用循环链表结合一个带模的计数器,计数器递增的同时链表向前遍历,计数器抵达指定次数时将链表当前节点从环中删除,如此往复直至最终剩余规定人数。
var Node = function(element){
this.element = element;
this.next = null;
};
var LinkedList = function(){
this.head = new Node();
this.head.next = this.head;
this.findPrev = function(item){
var prev, node = this.head;
while(node.next!==this.head){
prev = node;
node = node.next;
if(node===item)
return prev;
}
return -1;
};
this.append = function(item){
var node = this.head;
while(node.next!==this.head){
node = node.next;
}
item.next = node.next;
node.next = item;
};
this.remove = function(item){
var prev = this.findPrev(item);
if(prev!==-1){
prev.next = item.next;
delete item;
return true;
}
return false;
}
this.toString = function(){
var result = 'head', node = this.head;
while(node.next){
node = node.next;
result += (' > ' + node.element);
}
return result;
}
}
var findSurvivor = function(){
var i, l = new LinkedList();
for(i=1;i<42;i++){
l.append(new Node(i));
}
console.log('Once upon a time, there\'re 41 men trapped.');
console.log('Some of them decided to kill themselves.');
console.log('While two of them would rather not.');
console.log('How do they survive?');
var count = 0, left =41, node = l.head.next;
while(left>2){
var tmp = node;
node = node.next;
if(count===2){
console.log(tmp.element + ' is going to kill himself.');
l.remove(tmp);
left--;
}
count = (count + 1) % 3;
if(node===l.head)
node = node.next;
}
console.log('In the end, ' + l.head.next.element + ' and ' + l.head.next.next.element + ' survived.');
}