单向环形链表

• 单向环形链表最经典的问题就是约瑟夫问题(Josephu).

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

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

完成对单向环形链表的添加节点，删除节点和显示；

package main

import "fmt"

//定义猫的结构体节点
type CatNode struct {
    no   int //猫的编号
    name string
    next *CatNode
}

//环形链表中的head节点是需要存放数据的；
func InsertCatNode(head *CatNode, newCatNode *CatNode) {

    //判断是不是添加第一只猫；
    if head.next == nil {
        head.no = newCatNode.no
        head.name = newCatNode.name
        head.next = head //构成只有一个节点的环形；
        fmt.Println(newCatNode, "已经加入到环形链表中")
        return
    }

    //定义一个临时的变量，帮忙找到环形的最后节点：
    temp := head
    for {
        if temp.next == head {
            break
        }
        temp = temp.next
    }
    //加入到链表中；
    temp.next = newCatNode
    newCatNode.next = head
}

//输出一个猫节点：
/*
1.先让temp指向head；
2.让helper指向环形链表最后；
3.让temp和要删除的id进行比较，如果相同，则通过helper完成删除；
    【这里必须考虑，如果删除的就是头结点怎么办？】
*/
func DelCatNode(head *CatNode, id int) *CatNode {
    temp := head
    helper := head

    //判断是否为空链表
    if temp.next == nil {
        fmt.Println("这是一个空的环形链表，不能删除")
        return head
    }

    //如果只有一个节点：
    if temp.next == head { //只有一个节点；
        if temp.no == id {
            temp.next = nil
        }
        return head
    }

    //将helper定位到链表最后
    for {
        if helper.next == head {
            break
        }
        helper = helper.next
    }

    //如果有两个[包含两个]以上节点
    flag := true
    for {
        if temp.next == head { //如果到这来，说明我比较到最后一个[最后一个还没比较]
            break
        }

        if temp.no == id {
            if temp == head { //说明删除的是头节点
                head = head.next
            }

            //恭喜找到，我们可以在这里直接删除：
            helper.next = temp.next
            fmt.Printf("猫猫=%d，已删除\n", id)
            flag = false
            break
        }
        temp = temp.next     //移动 [比较]
        helper = helper.next //移动 [一旦找到要删除的节点 helper]
    }

    //这里还要比较一次；
    if flag { // 如果flag为真，则我们上面没有删除
        if temp.no == id {
            helper.next = temp.next
            fmt.Printf("猫猫=%d,已删除\n", id)
        } else {
            fmt.Printf("对不起，没有no=%d\n", id)
        }
    }
    return head
}

//输出环形的链表：
func ListCircleLink(head *CatNode) {
    fmt.Println("环形链表的具体情况如下:")
    temp := head
    if temp.next == nil {
        fmt.Println("empty link.")
        return
    }

    for {
        fmt.Printf("猫的信息为=[id=%d, name=%s] -->\n", temp.no, temp.name)
        // fmt.Println(temp)
        if temp.next == head {
            break
        }
        temp = temp.next
    }

}

func main() {

    //初始化一个环形链表的头节点；
    head := &CatNode{}

    //创建一只猫，
    cat1 := &CatNode{
        no:   1,
        name: "tom",
    }
    cat2 := &CatNode{
        no:   2,
        name: "jerry",
    }
    cat3 := &CatNode{
        no:   3,
        name: "tony",
    }
    InsertCatNode(head, cat1)
    InsertCatNode(head, cat2)
    InsertCatNode(head, cat3)
    ListCircleLink(head)
    head = DelCatNode(head, 30) //要求删除不存在的节点；
    ListCircleLink(head)
    head = DelCatNode(head, 3) //删除尾部节点；
    ListCircleLink(head)
    head = DelCatNode(head, 1) //删除头部节点；
    ListCircleLink(head)
}