最近楼主在看麦克米伦的《数据结构与算法JavaScript描述》一书，其中链表有个习题挺有趣，内容是这样的：
传说在公元1世纪的犹太战争中，犹太历史学家弗拉维奥·约瑟夫斯和他的40个同胞被罗马士兵包围。犹太士兵决定宁可自杀也不做俘虏，于是商量出了一个自杀方案。他们围成一个圈，从一个人开始，数到第三个人时将第三个人杀死，然后再数，直到杀光所有人。约瑟夫和另外一个人决定不参加这个疯狂的游戏，他们快速地计算出了两个位置，站在那里得以幸存。写一段程序将n个人围成一圈，并且第m个人会被杀掉，计算一圈人中哪两个人最后会存活。使用循环链表解决该问题
于是决定实现一下：全文源码如下
<template>
<div id="testActivity" class="main">
<el-form :model="form" class="demo-form-inline">
<el-form-item label="">
<el-input v-model="form.value" placeholder="请输入要排队的序列,以逗号分隔" clearable @input="inputChange" />
</el-form-item>
<el-form-item label="">
<el-input v-model="form.delValue" placeholder="请输入从第几个开始删" clearable @input="delValueChange" />
</el-form-item>
<el-form-item>
<el-button type="primary" @click="onSubmit">计算</el-button>
</el-form-item>
<p v-if="result">剩下的是：{{ result }}</p>
</el-form>
</div>
</template>
<script>
var person = [] // 存放队列
var len = 3 // 从第几个开始删，默认第3个
// 替换中文逗号
function ReplaceChina(obj) {
while (obj.indexOf('，') !== -1) {
obj = obj.replace(/，/ig, ',')
}
return obj
}
// LList类提供了对链表进行操作的方法。该类的功能包括插入删除节点、在列表中查找给定的值
function LList() {
this.head = new Node('head')
this.head.next = this.head
this.find = find
this.insert = insert
this.display = display
this.findPrevious = findPrevious
this.remove = remove
}
// Node类包含两个属性：element用来保存节点上的数据，next用来保存指向下一个节点的链接
function Node(element) {
this.element = element
this.next = null
}
// 从链表中删除节点时，需要先找到待删除节点前面的节点。找到这个节点后，修改它的next属性，使其不再指向待删除节点，而是指向待删除节点的下一个节点。
function findPrevious(item) {
var currNode = this.head
while (currNode.next.element !== item) {
currNode = currNode.next
}
return currNode
}
// 显示结果
function display() {
var currNode = this.head
const arr = []
while (currNode.next.element !== 'head') {
arr.push(currNode.next.element)
currNode = currNode.next
}
return arr
}
// 辅助方法find()，该方法遍历链表，查找给定数据
function find(item) {
var currNode = this.head
while (currNode.element !== item) {
currNode = currNode.next
}
return currNode
}
// 插入一个节点
// 将新节点的next属性设置为“后面”节点的next属性对应的值。然后设置“后面”节点的next属性指向新节点
function insert(newElement, item) {
var newNode = new Node(newElement)
var current = this.find(item)
newNode.next = current.next
current.next = newNode
}
// 删除方法
function remove(item) {
var prevNode = this.findPrevious(item) // 上一个节点
let nextDel = prevNode.next // 下一个需要删除的节点
prevNode.next = prevNode.next.next // 删除item节点（把item上一个节点的指针指向item的下一个节点，即删除了item)
let i = 0
while (i < len) { // 找到第len个的元素，即下次要删除的节点
if (nextDel.next.element === 'head') { // 如果到了最开头，则向后移一位，并退出此次循环，并不累计i的值
nextDel = nextDel.next
continue
}
nextDel = nextDel.next
i++
}
return nextDel // 返回下次要删除的节点
}
export default {
name: 'TestActivity',
data() {
return {
form: {
value: '',
delValue: ''
},
result: '',
person: []
}
},
mounted() {
},
methods: {
delValueChange(val) {
len = Number(val) // 格式化为数值类型
},
inputChange(val) {
person = val.split(',')// 把字符串存入队列数组
},
// 点击计算按钮，开始计算
onSubmit() {
// 一些校验
if (!this.form.value || !this.form.delValue) {
this.$alertMessage('error', '请输入必填项')
return
}
const timesString = ReplaceChina(this.form.value) // 替换中文分号
person = timesString.split(',')
if (this.form.delValue > person.length) {
this.$alertMessage('error', '开始删除的位置不能大于队列总数')
return
}
const first = 'head'
let i = 0
const cities = new LList() // 实例化一个实例
// 把person数组放入cities链表
while (i < person.length) {
if (i === 0) {
cities.insert(person[0], first)
} else {
const j = i - 1
cities.insert(person[i], person[j])
}
i++
}
// 显示当前排队情况
cities.display()
const length = len - 1
let delName = person[length] // 当前要删掉的节点
// 循环去删掉节点，留下最后2个
while (person.length > 2) {
delName = cities.remove(delName).element
person = cities.display()
this.result = person.join(',')// 最后的结果
}
}
}
}
</script>
<style scoped>
.main{
padding: 20px ;
}
</style>
因为只是简单实现一下功能，所以代码还有很多不完善的地方，大佬轻喷哈~