Golang约瑟夫问题

package main

import "fmt"

type Person struct {
    Number int
    Next   *Person
}

// 编写一个函数，构成单向的环形链表
// number: 表示小孩的个数
// *Person: 返回该环形的链表的第一个人的指针
func AddPerson(number int) (first *Person) {
    //判断
    if number == 1 {
        fmt.Println("人数不能小于1")
        return first
    }
    // 临时当前结点
    current := &Person{}
    //循环的构建这个环形链表
    for i := 1; i <= number; i++ {
        person := &Person{Number: i}
        // 分析构成循环链表，需要一个辅助指针[帮忙的]
        // 1. 因为第一个结点比较特殊
        if i == 1 {
            first = person
            current = person
            current.Next = first
        } else {
            current.Next = person
            // 当前临时结点位移
            current = person
            //构造环形链表
            current.Next = first
        }
    }
    return
}

func ShowPersonLink(first *Person) {
    //处理一下如果环形链表为空
    if first.Next == nil {
        fmt.Println("链表为空...")
        return
    }

    //创建一个指针，帮助遍历.[说明至少有一个结点]
    current := first
    fmt.Println("打印:")
    for {
        fmt.Printf("  Number: %d->", current.Number)
        // 退出的条件?current.Next == first
        if current.Next == first {
            break
        }
        // current移动到下一个
        current = current.Next
    }
    fmt.Println()
}

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

// 分析思路
// 1.编写一个函数，PlayGame(first *Person, startNumber int, countNum int)
// 2.最后我们使用一个算法，按照要求，在环形链表中留下最后一个人
func PlayGame(first *Person, startNumber int, countNum int) {
    // 1.空的链表我们单独的处理
    if first.Next == nil {
        fmt.Println("空的链表, 没有结点...")
        return
    }
    // 定义一个每次删除结点的上一个结点
    tail := first
    // 初始化临时结点到尾部
    for {
        if tail.Next == first {
            break
        }
        tail = tail.Next
    }
    // 3.初始化, 让first移动到startNumber结点, tail移动到startNumber上一个结点
    for i := 1; i <= startNumber-1; i++ {
        first = first.Next
        tail = tail.Next
    }
    // 4.开始数 countNum, 然后就删除first指向的结点
    for {
        for i := 1; i <= countNum-1; i++ {
            first = first.Next
            tail = tail.Next
        }
        fmt.Printf("编号:%4d出圈 \n", first.Number)
        //删除first执行的结点
        first = first.Next
        tail.Next = first
        // 判断如果 tail == first, 圈子中只有一个结点.
        if tail == first {
            break
        }
    }
    fmt.Printf("编号:%4d存活\n", first.Number)
}

func main() {
    first := AddPerson(500)
    ShowPersonLink(first)
    PlayGame(first, 20, 31)
}

有疑问加站长微信联系（非本文作者）