《数据结构与算法JavaScript描述》- 第六章 链表

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

//Node对象定义
function Node(element) {
    this.element = element;
    this.next = null;
}
//LList对象定义
function LList() {
    this.head = new Node("head");
    this.find = find;
    this.insert = insert;
    this.remove = remove;
    this.findPrevious = findPrevious;
    this.display = display;
}

function find(item) {
    var currNode = this.head;
    while (currNode.element != item) {
        currNode = currNode.next;
    }
    return currNode;
}

function insert(element, item) {
    var newNode = new Node(element);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

function findPrevious(item) {
    var current = this.head;
    while (current.next.element != item && current.next != null) {
        current = current.next;
    }
    return current;
}

function remove(item) {
    var prevNode = this.findPrevious(item);
    if (prevNode.next != null)
        prevNode.next = prevNode.next.next;
}

function display() {
    var str = "";
    var current = this.head;
    while (current.next != null) {
        str += current.next.element + "\n";
        current = current.next;
    }
    return str;
}

function Node(element) {
    this.element = element;
    this.next = null;
}

function LList(num) {
    var head = new Node(1);
    var p = head;
    for (var i = 2; i <= num; i++) {
        var temp = new Node(i);
        p.next = temp;
        p = temp;
    }
    p.next = head;
    return head;
}

var cirLinkList = new LList(42);

var current = cirLinkList;

var arr = [];
// console.log(current.next.next.next)

// 每次遍历删除一个节点
while (current.next.next != current) {
    for (var i = 1; i < 4; i++) {
        var parent = current;
        current = current.next;
    }
    //删除节点的本质即改变其前一个元素的后继
    parent.next = current.next; // 删除节点
    arr.push(current.element); // 存储删除的节点数据
    current = parent.next; // 更新当前元素
}

console.log(current)

let tempArr = arr.sort(function (a, b) { 
    return a - b 
})

console.log(tempArr)