数据结构:环形链表-约瑟夫环
数据结构 About 2,638 words定义节点
type CircularNode struct {
No int
Next *CircularNode
}
定义环形链表
type CircularLinkedList struct {
first *CircularNode
}
初始化链表
func (list *CircularLinkedList) Init(nums int) {
if nums < 1 {
return
}
var temp *CircularNode
for i := 1; i <= nums; i++ {
node := &CircularNode{No: i}
if i == 1 {
list.first = node
list.first.Next = list.first
temp = list.first
} else {
temp.Next = node
node.Next = list.first
temp = temp.Next
}
}
}
出队列 方式一
因为是单链表,出队列需找到需要出队列的前一个节点。
首先找到开始节点的前一个节点。其次定义计数器,开始循环遍历,若计数器等于间隔数减1
时将节点出队列,并重置计数器,反之计数器累加,指针后移。
func (list *CircularLinkedList) Pop(listLen, startNo, interval int) {
if startNo < 1 || startNo > listLen {
fmt.Println("参数不合法")
return
}
temp := list.first
// 找开始节点的前一个节点
for {
if temp.Next.No == startNo {
break
}
temp = temp.Next
}
count := 0
for {
if count+1 == interval {
fmt.Println("出圈 No#", temp.Next.No)
if temp == temp.Next { // 只剩下一个节点
break
}
count = 0
temp.Next = temp.Next.Next
continue
}
count++
temp = temp.Next
}
}
出队列 方式二
首先找到开始节点的前一个节点temp
。然后再定义一个指针temp2
指向开始节点,每次将temp
和temp2
指针移动指定间隔数减1
次(因为单链表删除节点,需借助删除节点的前一个节点),最后将temp2
赋值为temp2
的下一个节点,
func (list *CircularLinkedList) Pop2(listLen, startNo, interval int) {
if startNo < 1 || startNo > listLen {
fmt.Println("参数不合法")
return
}
temp := list.first
// 找开始节点的前一个节点
for {
if temp.Next.No == startNo {
break
}
temp = temp.Next
}
countPointer := temp.Next // 指向开始节点
for {
if temp == countPointer {
fmt.Println("出圈 No#", countPointer.No)
break
}
for i := 0; i < interval-1; i++ {
countPointer = countPointer.Next
temp = temp.Next
}
fmt.Println("出圈 No#", countPointer.No)
countPointer = countPointer.Next
temp.Next = countPointer
}
}
测试代码
func main() {
circularLinkedList := &CircularLinkedList{}
circularLinkedList.Init(5)
circularLinkedList.Print()
circularLinkedList.Pop(5, 1, 1)
//circularLinkedList.Pop2(5, 1, 2)
}
func (list *CircularLinkedList) Print() {
temp := list.first
for temp != nil {
fmt.Println("No#", temp.No)
if temp.Next == list.first {
return
}
temp = temp.Next
}
}
Views: 1,714 · Posted: 2021-01-21
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...