单向环形链表的应用实例：

• Josephu问题：

 设编号为1,2,....n的n个人围坐一圈，
约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列；
以此类推，知道所有人出列为止，由此产生一个出队编号的序列。

• 提示：

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

思路分析

• 1.编写一个函数，PlayGame(first *Boy,startNo int,CountNo int) {}
• 2.最后我们使用一个算法，按照要求，在环形链表中留下最后一人。

package main

import "fmt"

//小孩的结构体
type Boy struct {
    No   int  //编号；
    next *Boy //指向下一个小孩的指针；
}

// 编写一个函数，构成单向的环形链表
//num：小孩的个数；
//*Boy: 返回该环形链表的第一个小孩的指针,默认值是nil；
func AddBoy(num int) *Boy {

    first := &Boy{}  //空节点
    curBoy := &Boy{} //辅助指针；
    //判断
    if num < 1 {
        fmt.Println("num的值不对")
        return first
    }

    //循环的构建这个环形链表；
    for i := 1; i <= num; i++ {
        boy := &Boy{
            No: i,
        }
        //分析构成循环链表，需要一个辅助指针[帮忙的]
        //1.因为第一个小孩比较特殊
        if i == 1 { //第一个小孩
            first = boy //不能动，一直留在这里；
            curBoy = boy
            curBoy.next = first // 使得形成一个只有一个节点的环形链表；
        } else {
            curBoy.next = boy
            curBoy = boy
            curBoy.next = first //形成环形；
        }
    }
    return first
}

//显示单向的环形链表：[遍历]
func ShowBoy(first *Boy) {
    //处理一下：如果环形链表为空
    if first.next == nil {
        fmt.Println("链表为空，没有小孩")
        return
    }

    //创建一个辅助指针，帮助遍历； [说明至少有一个小孩]
    curBoy := first
    for {
        fmt.Printf("小孩标号=%d -> ", curBoy.No)
        //退出条件？
        if curBoy.next == first {
            break
        }
        //让curBoy移动到下一个：
        curBoy = curBoy.next
    }
    fmt.Println()
}

func PlayGame(first *Boy, startNo int, CountNo int) {
    //1.空的链表，单独处理一下：
    if first.next == nil {
        fmt.Println("空的链表，没有小孩")
        return
    }

    //判断，StartNo <= 小孩的总数
    //2.需要定义一个辅助的指针，帮助我们删除小孩；
    tail := first
    //3.让tail指向环形链表的最后一个小孩；
    //因为tail在删除小孩时使用；
    for {
        if tail.next == first { //说明tail到了最后的小孩
            break
        }
        tail = tail.next
    }

    //4.让first 移动到 startNo [后面删除小孩时，就以first为准；]
    for i := 1; i <= startNo-1; i++ {
        first = first.next
        tail = tail.next
    }
    //5.开始数countNo，然后就删除first 指向的小孩；
    for {
        //还是数countNo-1次
        for i := 1; i <= CountNo-1; i++ {
            first = first.next
            tail = tail.next
        }
        fmt.Printf("小孩编号为%d 出圈 \n", first.No)
        //删除first指向的节点；
        first = first.next
        tail.next = first

        //判断：如果tail == first，说明圈中只有一个小孩了；
        if tail == first {
            break
        }
    }
    fmt.Printf("小孩编号为%d 出圈 \n", first.No)
}

func main() {
    first := AddBoy(500)
    //显示
    ShowBoy(first)
    PlayGame(first, 20, 31)
}