Following the previous one-way list, the single line list can be further expanded into a ring, as shown in the following figure:
Characteristic:
1. The first node is called the head node, and the last node is called the tail node
2. Each node points to the next node unilaterally
3. Tail node next node points to head node
Title:
Gaspar, a French mathematician in the 17th century, told a story about 15 believers and 15 non believers who were in distress in the deep sea. Half of them had to be put into the sea, and the rest survived. So he thought of a way: 30 people in a circle, counting from the first one in turn, and throwing him into the sea every time they counted to the ninth one. This was a cycle Until there are only 15 people left. Ask how to arrange it so that every time you throw yourself into the sea, you are a non believer.
This is a typical Josephus ring problem, which can be solved by using a one-way list ring. The specific code is as follows:
package main
import "fmt"
type LinkNode struct {
Data interface{}
Next *LinkNode
}
type SingleLink struct {
head *LinkNode
tail *LinkNode
size int
}
//Initialize linked list
func InitSingleLink()(*SingleLink){
return &SingleLink{
head:nil,
tail:nil,
size:0,
}
}
//Get head node
func (sl *SingleLink)GetHead()*LinkNode{
return sl.head
}
//Get tail node
func (sl *SingleLink)GetTail()*LinkNode{
return sl.tail
}
//Print linked list
func (sl *SingleLink) Print(){
fmt.Println("SingleLink size:",sl.Length())
if sl.size == 0{
return
}
ptr := sl.GetHead()
headNode := sl.GetHead()
for ptr != nil{
fmt.Println("Data:",ptr.Data)
ptr = ptr.Next
if ptr.Next == headNode{
fmt.Println("Data:",ptr.Data)
break
}
}
}
//Length of linked list
func (sl *SingleLink) Length() int{
return sl.size
}
//Insert data (head insert)
func (sl *SingleLink) InsertByHead(node *LinkNode){
if node == nil{
return
}
//Determine whether the first node
if sl.Length() == 0{
sl.head = node
sl.tail = node
node.Next = nil
}else{
oldHeadNode := sl.GetHead()
sl.head = node
sl.tail.Next = node
sl.head.Next = oldHeadNode
}
sl.size++
}
//Insert data (trailer)
func (sl *SingleLink) InsertByTail(node *LinkNode) {
if node == nil{
return
}
//Insert first node
if sl.size == 0{
sl.head = node
sl.tail = node
node.Next = nil
}else{
sl.tail.Next = node
node.Next = sl.head
sl.tail = node
}
sl.size ++
}
//Insert data (subscript) location
func (sl *SingleLink) InsertByIndex(index int, node *LinkNode){
if node == nil{
return
}
//Insert into the head
if index == 0 {
sl.InsertByHead(node)
}else{
if index > sl.Length(){
return
}else if index == sl.Length(){
//Add nodes to tail
sl.InsertByTail(node)
}else{
preNode := sl.Search(index-1) //Previous node with index as subscript
currentNode := sl.Search(index) //Nodes with index as subscript
preNode.Next = node
node.Next = currentNode
sl.size++
}
}
}
//Delete data (subscript) location
func (sl *SingleLink) DeleteByIndex(index int) {
if sl.Length() == 0 || index > sl.Length(){
return
}
//Delete first node
if index == 0{
sl.head = sl.head.Next
sl.tail.Next = sl.head
}else{
preNode := sl.Search(index-1)
if index != sl.Length()-1{
nextNode := sl.Search(index).Next
preNode.Next = nextNode
}else{
sl.tail = preNode
preNode.Next = sl.head
}
}
sl.size--
}
//Query data
func (sl *SingleLink) Search(index int)(node *LinkNode) {
if sl.Length() == 0 || index > sl.Length(){
return nil
}
//Head node or not
if index == 0{
return sl.GetHead()
}
node = sl.head
for i:=0;i<=index;i++{
node = node.Next
}
return
}
func (sl *SingleLink)pop(){
popIndex := 8
delNode := sl.Search(popIndex)
fmt.Println("POP node : ",delNode.Data)
sl.DeleteByIndex(popIndex)
sl.tail = sl.Search(popIndex - 1)
sl.head = sl.Search(popIndex)
fmt.Printf("Head:%v , Tail:%v\n",sl.head.Data,sl.tail.Data)
}
func main() {
//Initialize linked list
sl := InitSingleLink()
//Generate rings of 30 elements
for i:=0;i<30;i++{
snode := &LinkNode{
Data:i,
}
sl.InsertByIndex(i,snode)
}
//Cycle out element 9
var round int
for sl.size > 15{
fmt.Printf("================ Round %d ================\n",round)
sl.pop()
round ++
}
//Winner
fmt.Println("================ Finish ================")
fmt.Println("People who survived.")
sl.Print()
}results of enforcement
================ Round 0 ================ POP node : 9 Head:10 , Tail:8 ================ Round 1 ================ POP node : 19 Head:20 , Tail:18 ================ Round 2 ================ POP node : 29 Head:0 , Tail:28 ================ Round 3 ================ POP node : 10 Head:11 , Tail:8 ================ Round 4 ================ POP node : 21 Head:22 , Tail:20 ================ Round 5 ================ POP node : 2 Head:3 , Tail:1 ================ Round 6 ================ POP node : 14 Head:15 , Tail:13 ================ Round 7 ================ POP node : 26 Head:27 , Tail:25 ================ Round 8 ================ POP node : 8 Head:11 , Tail:7 ================ Round 9 ================ POP node : 23 Head:24 , Tail:22 ================ Round 10 ================ POP node : 6 Head:7 , Tail:5 ================ Round 11 ================ POP node : 22 Head:24 , Tail:20 ================ Round 12 ================ POP node : 7 Head:11 , Tail:5 ================ Round 13 ================ POP node : 25 Head:27 , Tail:24 ================ Round 14 ================ POP node : 13 Head:15 , Tail:12 ================ Finish ================ People who survived. SingleLink size: 15 Data: 15 Data: 16 Data: 17 Data: 18 Data: 20 Data: 24 Data: 27 Data: 28 Data: 0 Data: 1 Data: 3 Data: 4 Data: 5 Data: 11 Data: 12