谁能活下来——链表实践

发表于   |   分类于

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

问题描述

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
function Node(element){
    this.element = element;
    this.next = null;
}
function LList(){
    this.head = new Node('head');
    this.head.next = this.head;
    this.insert = insert;
    this.remove = remove;
    this.find = find;
    this.display = display;
    this.back = back;
}
function find(item){
    let currentNode = numbers.head;
    while(currentNode.element !== item){
        currentNode = currentNode.next;
    }
    return currentNode;
}
function previous(item){
    let current = numbers.head;
    while(current.next.element !== item ){
        current = current.next;
    }
    return current;
}
function insert(ele, item){
    let newNode = new Node(ele);
    let current = find(item);
    newNode.next = current.next;
    current.next = newNode;
}
function remove(ele){
    let previousNode = previous(ele);
    previousNode.next = previousNode.next.next;
}
function back(current, n){
    while(n > 0){
        if(current.next.element !== numbers.head.element){
            n--;
        }
        current = current.next;
    }
    return current;
}
function display(){
    let elements = [];
    let current = numbers.head.next;
    while(current.element !== numbers.head.element){
        elements.push(current.element);
        current = current.next;
    }
    return elements.join(' ');
}
function kill(){
    let current = numbers.head.next;
    while(numbers.back(current, step-1).element !== current.element){
        numbers.remove(numbers.back(current, step-1).element);
        current = numbers.back(current, step-1);
    }
}
var numbers = new LList();
var total = 8;
var step = 4;
for(let i=1; i<=total; i++){
    if(i===1){
        numbers.insert(i, 'head');
    }else{
        numbers.insert(i, i-1);
    }
}
console.log('all:');
console.log(numbers.display());
kill();
console.log('live');
console.log(numbers.display());