1.1.1. 一、什么是约瑟夫（Josephu）问题：

Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推， 直到所有人出列为止，由此产生一个出队编号的序列。

1.1.2. 二、用单向循环链表解决约瑟夫问题。

1、分析：

用一个不带头结点的单向循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除。

2、代码实现：

• 节点的结构：

// 链表
type Persion struct {
    Num  int
    Next *Persion // 下一个节点
}

• 创建一个有 num 个节点的单向的环形链表。

// 创建一个有 num 个节点的单向的环形链表
// 返回第一个节点
func AddNodes(num int) *Persion {

    first := &Persion{}   //第一个结点
    curNode := &Persion{} //空结点

    //判断
    if num < 1 {
        fmt.Println("num 的值不对")
        return first
    }
    //循环的构建这个环形链表
    for i := 1; i <= num; i++ {
        newNode := &Persion{Num: i,}
        if i == 1 { //第一个节点
            first = newNode
            curNode = newNode
            curNode.Next = first
        } else {
            curNode.Next = newNode
            curNode = newNode    //curNode往下移动
            curNode.Next = first //构造环形链表
        }
    }
    return first
}

• 显示链表。

//显示
func ShowPersion(first *Persion) {
    //处理一下如果环形链表为空
    if first.Next == nil {
        fmt.Println("链表为空，没有节点...")
        return
    }

    //从 first 开始遍历
    curNode := first
    for {
        fmt.Printf("编号=%d ->", curNode.Num)
        //遍历到最后
        if curNode.Next == first {
            break
        }
        //动到下一个
        curNode = curNode.Next
    }
}

• 解决约瑟夫问题。

//约瑟夫问题。
/**
    first :第一个节点
    startNo :从第几个节点开始计数
    countNum ：计数多少次。才删除节点。
*/
func PlayGame(first *Persion, startNo int, countNum int) {

    //空的链表我们单独的处理
    if first.Next == nil {
        fmt.Println("空的链表，没有节点")
        return
    }
    //定义辅助变量，帮助我们删除节点。tail 永远设置为 first 的前一个。
    tail := first
    for {
        if tail.Next == first { //说明 tail 到了最后
            break

        }
        tail = tail.Next
    }

    //让 first  移动到 startNo。tail 永远设置为 first 的前一个。
    for i := 1; i <= startNo-1; i++ {
        first = first.Next
        tail = tail.Next
    }
    fmt.Println()
    //开始数 countNum,  然后就删除 first 指向的节点
    for {

        //开始数 countNum 次，找到要删除的元素first
        for i := 1; i <= countNum-1; i++ {
            first = first.Next
            tail = tail.Next

        }
        fmt.Printf("节点编号为%d 出圈 \n", first.Num)
        //删除 first 节点
        first = first.Next // 往下移动一个节点
        tail.Next = first // 删除原来的first
        //判断如果 tail == first,  圈子中只有一个节点.
        if tail == first {
            break
        }
    }

    fmt.Printf("最后一个节点编号为%d 出圈 \n", first.Num)

}

关键点：

1、first 是要删除的节点。

2、tail 永远设置为 first 的前一个（也就是first 往前移动几次，tail 也跟着往前移动几次）。方便删除的时候使用tail。

• 测试：

func main() {
    //创建链表
    first := AddNodes(5)
    // 显示
    ShowPersion(first)
    //约瑟夫问题
    PlayGame(first, 3, 4)
}