数据结构题目28：约瑟夫问题

题目：约瑟夫问题：一直有n个人（不妨以编号1，2，3，...，n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依次规则重复下去，知道圆桌周围的人全部出列。
例如：当n=8，m=4，k=3时，出列的顺序依次为6，2，7，4，3，5，1，8。

解题思路：解决约瑟夫问题可以利用多种数据结构，但比较简单和自然的方法是利用一个具有n个链结点，且不带头结点的循环链表。将圆桌周围的每一个人对应着该链表中的一个链结点，某个人出列相当于从链表中删除一个链结点。下面的算法就是在该循环链表中不断的报数，不断的删除一个链结点，直到循环链表中还剩一个链结点时游戏结束。
整个算法可以分为以下3步：
1.建立一个具有n个链结点，且无头结点的循环链表
2.确定第1个报数点的位置
3.不断地从链表中删除一个链结点，直至链表中只剩有一个链结点

具体实现如下：

//定义链结点
class Node{
    constructor (data, link) {
        this.data = data,
        this.link = link
    }
}
function  JOSEPHUS(n, m, k) {
    let p, r, list = null
    let i

    //建立一个无头结点的循环链表
    for (i = 1; i <= n; i++) {
        p = new Node(i, null)
        if ( list==null ) {
            list = p
        } else {
            r.link = p
        }
        r = p
    }
    p.link = list
    //至此一个循环链表创建完了

    p = list
    for (i = 1; i < k; i++) {
        r = p
        p = p.link
    }
    //此时p指向第1个出发结点

    while ( p.link!=p ) {
        for (i = 1; i < m; i++) {
            r = p
            p = p.link
        }
        r.link = p.link
        console.log("出列的是："+p.data)
        p = null
        p = r.link
    }
    console.log("最后出列的是："+p.data)
}
JOSEPHUS(8, 4, 3)