环形链表的一种Go语言实现
package mainimport "fmt"//定义一个环形链表的节点构造体type circleSingleLink struct { id int name string next *circleSingleLink}//插入节点到环形链表func Insert(head, newnode *circleSingleLink) { //判断是否为空链表 if head.next == nil{ //如果为空则把增加的第一个元素给头节点，这里和其余链表有些区别，其余链表头结点是空的 head.id = newnode.id head.name = newnode.name //重点是要让一个节点也造成一个环形，即收尾相接 head.next = head return } //增加非头结点到环形链表 temp := head for{ if temp.next == head { //尾部增加 temp.next = newnode newnode.next = head break } temp = temp.next }}//显示环形链表的所有节点信息func CircleList(head *circleSingleLink){ //判断链表是否为空 if head.next == nil { fmt.Println("链表为空") return } temp := head for { fmt.Printf("[%d %s] -> ", temp.id, temp.name) //留神这里是这样判断终止条件的 if temp.next == head{ break } temp = temp.next }}//删除环形链表的一个节点(难点)func CircleDelete(head, node *circleSingleLink) *circleSingleLink { //之所以有返回值是因为头结点的值和指向要发生变化 //删除思路： //先让temp 指向head //再让helper指向环形链表的最初 //让temp和要删除的节点比拟，如果雷同，则让helper实现删除节点，重点是要思考是否为头结点，因为环形链表的头结点有值 temp := head if temp.next == nil { //链表为空的时候 fmt.Println("链表为空") return head } if temp.next == head { //只有一个头结点的环形链表 temp.next = nil return head } helper := head for { if helper.next == head { break } helper = helper.next //将指针定位到环形链表的尾节点 } //如果有两个及以上的节点 for { if temp.next == head { //阐明到最初一个并且还没判断是否是要删除的节点 if temp.id == node.id { helper.next = temp.next }else { fmt.Println("没有该节点") } break } if temp.id == node.id { //找到了要删除的节点 if temp == head { //如果删除的是头结点 head = head.next } //删除非头结点 helper.next = temp.next //helper始终在temp的后一个 break } temp = temp.next //用作比拟 helper = helper.next //用作操作 } return head}func main(){ //定义一个链表的头 head := &circleSingleLink{} //定义第一个节点 node1 := &circleSingleLink{ id: 1, name : "number1", } node2 := &circleSingleLink{ id: 2, name : "number2", } node3 := &circleSingleLink{ id: 3, name : "number3", } Insert(head, node1) Insert(head, node2) Insert(head, node3) head = CircleDelete(head, node1) CircleList(head)}约瑟夫问题：
package mainimport "fmt"type Boy struct { id int next *Boy}//创立一个环形链表,并返回头指针func CreateLink(num int) *Boy { first := &Boy{} //头指针不能动，因而须要一个辅助指针进行循环创立 curBoy := &Boy{} if num < 1 { return first } for i := 1; i <= num; i++ { boy := &Boy{ id: i, next: nil, } 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.id) if curBoy.next == first { break } curBoy = curBoy.next }}//应用环形链表实现约瑟夫问题func PlayGame(first *Boy, startNo int, countNum int) { //空链表的状况 if first.next == nil { fmt.Println("链表为空，游戏完结") return } //定义两个指针循环，其中first负责比拟，tail负责删除 tail := first //将tail斧正定位到链表的最初 for { if tail.next == first { break } tail = tail.next } //开始挪动startNo-1步 for i := 0; i < startNo -1; i++ { first = first.next tail = tail.next } fmt.Println() //开始循环删除环形链表中第countNum-1个节点 for { for i := 0; i < countNum - 1; i++ { first = first.next tail = tail.next } //打印行将出圈的节点信息 fmt.Printf("编号为%d的节点出圈\n", first.id) //删除此时first指向的以后节点 first = first.next tail.next = first //确定完结条件 if tail == first { break } } //打印最初一个出圈的节点 fmt.Printf("编号为%d的节点出圈\n", first.id)}func main(){ first := CreateLink(51) ShowBoy(first) PlayGame(first, 2, 3)}