const {CircleDoublyList} = require("ss-linked-list");
// 使用双向循环链表实现
function Josephus(n, start, k){
var numberArr = Array.from(new Array(n),(val,index)=>index+1);
var list = new CircleDoublyList(...numberArr);
var currentNode = list.getNode(start - 1);
var result = [];
while(n--){
for(var i = 0; i < k - 1; i++){
currentNode = currentNode.next;
}
result.push(currentNode.value);
currentNode.prev.next = currentNode.next;
currentNode.next.prev = currentNode.prev;
currentNode = currentNode.next;
}
return result;
}
Josephus(9, 1, 5);
const {CircleSinglyList} = require("ss-linked-list");
// 使用单向循环链表实现
function Josephus2(n, start, k){
var numberArr = Array.from(new Array(n),(val,index)=>index+1);
var list = new CircleSinglyList(...numberArr);
var currentNode = list.getNode(start - 1);
var result = [];
var tobeDeleted = null;
while(n--){
// 到目的地前一个停下
for(var i = 0; i < k - 2; i++){
currentNode = currentNode.next;
}
tobeDeleted = currentNode.next;
result.push(tobeDeleted.value);
currentNode.next = currentNode.next.next;
currentNode = currentNode.next;
}
return result;
}
Josephus2(9, 1, 5);
no comments
sign in to comment