Skip to content

Commit 081e389

Browse files
ruyuejunruyuejun
committed
修正循环链表
1 parent 2e2c56a commit 081e389

File tree

3 files changed

+187
-53
lines changed

3 files changed

+187
-53
lines changed

‎02-数据结构/01-线性表5-循环链表.md‎

Lines changed: 17 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@
2525
// 创建循环链表
2626
func New() *RingList {
2727
head := &node{0, nil} // 头节点存储链表中元素的个数
28+
head.next = head
2829
return &RingList{
2930
head,
3031
}
@@ -40,12 +41,19 @@
4041
// 增加：末尾添加
4142
func (ll *RingList) Append(data interface{}){
4243

43-
insertNode := &node{data, ll.head} // 要插入的节点
44+
insertNode := &node{data, nil} // 要插入的节点
4445
var len int = 0
4546
len = ll.head.data.(int)
4647

4748
// 查询最后一个节点
4849
lastNode := ll.head.next
50+
51+
if len == 0 {
52+
53+
} else {
54+
55+
}
56+
4957
if lastNode == nil { // 第一次添加
5058
ll.head.next = insertNode
5159
len ++
@@ -140,12 +148,18 @@
140148

141149
问题：
142150
```
143-
编号从1,2,3....到n的人围成一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的人出列。
144-
出列后，下一位从1开始继续报数，数到m出列，依次类推，直到所有人出列，产生一个出列的序列。
151+
约瑟夫混入了40个犹太人群中，最后被敌军围困在山洞，他们决定宁死不降。
152+
这41人围坐成了1圈，决定从其中1人开始报数，每次报数到3，那个人必须自杀，死后下一个人从1重新报数。
153+
约瑟夫该如何安排位置才能让自己逃离这个死亡游戏？
145154
```
146155

147156
提示：
148157
```
149158
使用循环链表来处理，每次到m，删除链表中对应节点，然后再从1开始计数，直到链表长度变为0
159+
答案：16与31
150160
```
151161

162+
解法：
163+
```go
164+
165+
```

‎sources/go/list/RingList/RingList.go‎

Lines changed: 100 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@
2323
// 创建循环链表
2424
func New() *RingList {
2525
head := &node{0, nil} // 头节点存储链表中元素的个数
26+
head.next = head
2627
return &RingList{
2728
head,
2829
}
@@ -36,107 +37,141 @@
3637
}
3738

3839
// 增加：末尾添加
39-
func (ll *RingList) Append(data interface{}){
40+
func (rl *RingList) Append(data interface{}){
4041

41-
insertNode := &node{data, ll.head} // 要插入的节点
42+
insertNode := &node{data, rl.head} // 要插入的节点
4243
var len int = 0
43-
len = ll.head.data.(int)
44+
len = rl.head.data.(int)
4445

4546
// 查询最后一个节点
46-
lastNode := ll.head.next
47-
if lastNode == nil { // 第一次添加
48-
ll.head.next = insertNode
49-
len ++
50-
ll.head.data = len
51-
return
52-
}
53-
54-
for lastNode.next != nil { // 不是第一次添加
55-
lastNode = lastNode.next
47+
lastNode := rl.head.next
48+
49+
if len == 0 { // 第一次添加
50+
51+
insertNode.next = rl.head
52+
rl.head.next = insertNode
53+
54+
} else { // 不是第一次添加
55+
for lastNode.next != rl.head {
56+
lastNode = lastNode.next
57+
}
58+
lastNode.next = insertNode
5659
}
57-
lastNode.next = insertNode
60+
5861
len ++
59-
ll.head.data = len
60-
62+
rl.head.data = len
63+
6164
return
6265
}
6366

6467
// 增加：任意位置插入结点
65-
func (ll *RingList) Insert(index int, data interface{}) error{
68+
func (rl *RingList) Insert(index int, data interface{}) error{
6669

6770
var len int = 0
68-
len = ll.head.data.(int)
71+
len = rl.head.data.(int)
6972

7073
if index < 1 || index > len {
7174
return errors.New("index overflow")
7275
}
76+
77+
if index == len + 1 { // 如果是在末尾添加
78+
rl.Append(data)
79+
} else { // 如果不是在末尾添加
80+
81+
beforeNode := rl.head
82+
appendNode := &node{data, nil}
7383

74-
beforeNode := ll.head
75-
appendNode := &node{data, nil}
84+
for i := 0; i < index - 1; i++ {
85+
beforeNode = beforeNode.next // 找到要插入的位置的前置元素
86+
}
7687

77-
for i := 0; i < index - 1; i++ {
78-
beforeNode = beforeNode.next // 找到要插入的位置的前置元素
79-
}
80-
81-
appendNode.next = beforeNode.next
82-
beforeNode.next = appendNode
88+
appendNode.next = beforeNode.next
89+
beforeNode.next = appendNode
90+
}
8391

8492
len ++
85-
ll.head.data = len
93+
rl.head.data = len
8694

8795
return nil
8896

8997
}
98+
99+
// 删除：删除末尾节点
100+
func (rl *RingList) Pop() (interface{}, error) {
101+
102+
var len int = 0
103+
len = rl.head.data.(int)
104+
105+
if len == 0 {
106+
return nil, errors.New("list is empty")
107+
}
108+
109+
currentNode := rl.head
110+
for currentNode.next != rl.head {
111+
currentNode = currentNode.next
112+
}
113+
114+
len --
115+
rl.head.data = len
116+
currentNode.next = rl.head
117+
return currentNode.data, nil
118+
119+
}
90120

91121
// 删除：删除指定位置结点
92-
func (ll *RingList) Delete(index int) (interface{}, error) {
93-
94-
var len int = 0
95-
len = ll.head.data.(int)
122+
func (rl *RingList) Delete(index int) (interface{}, error) {
123+
124+
var len int = 0
125+
len = rl.head.data.(int)
96126

97-
if index < 0 || index >= len {
98-
return nil,errors.New("index overflow")
127+
if index <= 0 || index > len {
128+
return nil, errors.New("index overflow")
129+
}
130+
131+
if len == 0 {
132+
return nil, errors.New("list is empty")
133+
}
134+
135+
if index == len {
136+
return rl.Pop()
99137
}
100138

101-
currentNode := ll.head
102-
var beforeNode *node
139+
beforeNode := rl.head
103140
var delData interface{} // 被删除的数据
104141

105-
for i := 0; i < index; i++ {
106-
beforeNode = currentNode
107-
currentNode = currentNode.next
142+
for i := 0; i < index - 1; i++ {
143+
beforeNode = beforeNode.next
108144
}
109145

110-
beforeNode.next = currentNode.next
111-
currentNode = nil
146+
beforeNode.next = beforeNode.next.next
112147

113148
len--
114-
ll.head.data = len
149+
rl.head.data = len
115150

116151
return delData, nil
117152
}
118153

119154
// 查询： 获取指定位置结点
120-
func (ll *RingList) Node(index int) (interface{}, error) {
155+
func (rl *RingList) Node(index int) (interface{}, error) {
121156

122157
var len int = 0
123-
len = ll.head.data.(int)
158+
len = rl.head.data.(int)
124159

125-
if index < 0 || index >= len {
160+
if index < 0 || index > len {
126161
return nil, errors.New("index overflow")
127162
}
128-
currentNode := ll.head
163+
currentNode := rl.head
129164
for i := 0; i < index; i++ {
130165
currentNode = currentNode.next
131166
}
132167
return currentNode.data, nil
133168
}
134169

135170
// 打印链表
136-
func (ll *RingList) Show() {
171+
func (rl *RingList) Show() {
137172
var len int = 0
138-
len = ll.head.data.(int)
139-
currentNode := ll.head
173+
len = rl.head.data.(int)
174+
currentNode := rl.head
140175
for i := 0; i <= len; i++ {
141176
fmt.Print(currentNode.data)
142177
if i == len {
@@ -147,4 +182,21 @@
147182

148183
currentNode = currentNode.next
149184
}
185+
}
186+
187+
// 获取长度
188+
func (rl *RingList)Length() int {
189+
var len int = 0
190+
len = rl.head.data.(int)
191+
return len
192+
}
193+
194+
// 获取头结点
195+
func (rl *RingList)GetHead() *node{
196+
return rl.head
197+
}
198+
199+
// 获取下一个节点
200+
func (rl *RingList)GetNext(n *node) *node {
201+
return n.next
150202
}

‎sources/go/main.go‎

Lines changed: 70 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,8 +4,9 @@ import (
44
"algorithm/array"
55
SequenList "algorithm/list/SequenList"
66
LinkedList "algorithm/list/LinkedList"
7+
RingList "algorithm/list/RingList"
78
DoublyList "algorithm/list/DoublyList"
8-
"fmt"
9+
"fmt"
910
)
1011

1112
func testSparseArray() {
@@ -58,6 +59,24 @@ func testLinkedList() {
5859
fmt.Println(ll.Node(1))
5960
}
6061

62+
func testRingList() {
63+
64+
rl := RingList.New()
65+
rl.Show()
66+
67+
rl.Append(9)
68+
rl.Append(5)
69+
rl.Show()
70+
71+
rl.Insert(1,7)
72+
rl.Insert(3,4)
73+
rl.Show()
74+
75+
rl.Delete(3)
76+
rl.Show()
77+
78+
}
79+
6180
func testDoublyList() {
6281

6382
dl := DoublyList.New()
@@ -79,6 +98,51 @@ func testDoublyList() {
7998
dl.Show()
8099
}
81100

101+
// 约瑟夫环
102+
func testJosephus(){
103+
104+
// 生成循环链表
105+
rl := RingList.New()
106+
for i := 0; i < 41; i++ { // 多个人组成的循环链表
107+
rl.Append(i + 1) // 每个人都对应自己的原始编号
108+
}
109+
fmt.Print("生成的循环链表为：")
110+
rl.Show()
111+
112+
// 每次读取3个元素，读取位置从startNode开始
113+
startNode := rl.GetHead() // 起始开始报数的元素
114+
delIndex := 0 // 要删除元素的索引
115+
116+
for {
117+
118+
for i:= 1; i <= 3; i++ {
119+
120+
if rl.GetNext(startNode) == rl.GetHead() {
121+
delIndex = 1 // 每次从头结点开始时，删除索引变为0，重新记录
122+
startNode = rl.GetNext(rl.GetNext(startNode))
123+
} else {
124+
startNode = rl.GetNext(startNode)
125+
delIndex ++
126+
}
127+
128+
}
129+
130+
// 删除该元素
131+
val, _ := rl.Node(delIndex)
132+
fmt.Println("删除数据为：", delIndex, " ", val)
133+
rl.Delete(delIndex)
134+
135+
// 如果只有一个元素
136+
if rl.Length() < 3 {
137+
break;
138+
}
139+
}
140+
141+
fmt.Print("最终的循环链表为：")
142+
rl.Show()
143+
return
144+
}
145+
82146
func main() {
83147

84148
fmt.Println("start run...")
@@ -89,6 +153,10 @@ func main() {
89153

90154
// testLinkedList() // 测试单链表
91155

92-
testDoublyList() // 测试双向链表
156+
// testRingList() // 测试循环链表
157+
158+
testJosephus() // 测试约瑟夫环
159+
160+
// testDoublyList() // 测试双向链表
93161

94162
}

0 commit comments

Comments
 (0)