链表
目录
单向环形链表的案例
编号为1,2,3,4.。。。n，的n个人围成一个圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的人出列，下一个继续从一开始，数到m的人出列，依次类推直到所有人都出列为止。由此产生的一个出队的编号
以下代码都在一个go文件中
定义一个人员对象
type People struct {
No int
Next *People
}定义一个环形链表
type RingLinkedList struct {
First *People
}
func NewRingLinkedList() *RingLinkedList {
return &RingLinkedList{
First: nil,
}
}定义一个方法用于初始化环形链表
func (r *RingLinkedList) InitRingLinkedList(n int) *RingLinkedList {
// 如果n小于零，则需要返回空
if n <= 0 {
return nil
}
var currPeople *People = nil
for i := 1; i <= n; i++ {
// 处理第一个节点
if i == 1 {
r.First = &People{
No: i,
Next: nil,
}
// 形成环
r.First.Next = r.First
currPeople = r.First
} else {
// 将当前指针的下一个节点指向新创建的元素
currPeople.Next = &People{
No: i,
}
// 新创建的元素的下一个节点指向头结点
currPeople.Next.Next = r.First
// 当前节点下移
currPeople = currPeople.Next
}
}
return r
}定义方法读取环形链表
func (r *RingLinkedList) ShowRingLinkedList() {
currPeople := r.First
for {
fmt.Println(currPeople.No)
if currPeople.Next == r.First {
break
} else {
currPeople = currPeople.Next
}
}
}定义一个方法人员出列
func CountPeople(r *RingLinkedList, start int, countNum int) {
// 创建辅助指针指向first的前一个元素
fontPeople := r.First
for {
if fontPeople.Next == r.First {
break
}
fontPeople = fontPeople.Next
}
// 将first移动start-1次
for i := 0; i < start-1; i++ {
r.First = r.First.Next
fontPeople = fontPeople.Next
}
// 循环出圈
for {
// 判断只剩一个元素的情况
if fontPeople == r.First {
println(r.First.No)
break
} else {
// 将指针移动countNum-1次
for i := 0; i < countNum-1; i++ {
r.First = r.First.Next
fontPeople = fontPeople.Next
}
// 打印出圈中的元素
println(r.First.No)
// 删除头结点指向的元素
r.First = r.First.Next
fontPeople.Next = r.First
}
}
}测试
package ringlinkedlist
import "testing"
func TestRingLinkedList_InitRingLinkedList(t *testing.T) {
r := NewRingLinkedList()
r.InitRingLinkedList(10)
r.ShowRingLinkedList()
t.Log("----------------------------------")
CountPeople(r, 2, 3)
}结果
=== RUN TestRingLinkedList_InitRingLinkedList
1
2
3
4
5
6
7
8
9
10
ring_linked_list_test.go:10: ----------------------------------
4
7
10
3
8
2
9
6
1
5
--- PASS: TestRingLinkedList_InitRingLinkedList (0.03s)
PASS