数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Go语言程序：反转循环链表
本文将学习如何创建一个 Go 语言程序，使用递归和迭代方法反转循环链表。循环链表是一种链表，其中链表的最后一个节点指向第一个节点，形成一个循环。它可以用于实现循环缓冲区或轮询调度算法。
语法
func reverseList(head **Node){…}
reverseList() 函数用于反转循环链表。它接受指向头节点地址的指针作为参数。
func reverseList(current, prev, head *Node) *Node {…}
reverseList() 函数用于反转循环链表。它以第一个非头节点作为当前节点、nil 作为前一个节点以及列表的头节点作为参数。
方法一
在这个方法中，我们将使用迭代方法定义一个 reverseList() 函数，该函数用于反转循环链表。
算法
步骤 1 − 首先，我们需要导入 fmt 包。
步骤 2 − 然后，初始化一个 node 结构体来表示循环链表的元素。每个节点都有一个值和一个指向下一个节点的 next 指针。
步骤 3 − 现在，创建一个 nodeAdd() 函数，该函数将新节点添加到循环链表中。它创建一个具有给定值的新节点，并将其插入到头节点之后。
步骤 4 − 定义 printLinkedList() 函数来打印循环链表中所有节点的值。
步骤 5 − 现在，创建一个名为 reverseList() 的函数。它用于反转循环链表中节点的顺序。
步骤 6 − 此函数接收指向列表当前头的指针，迭代列表中的节点，并交换它们的 next 指针以反转顺序。
步骤 7 − 开始 main() 函数。在 main() 函数中，将几个节点插入循环链表。
步骤 8 − 现在，调用 reverseList() 函数并将头节点指针的值作为参数传递给函数。
步骤 9 − 此外，使用 fmt.Println() 函数将反转后的循环链表打印到屏幕上。
示例
以下是使用迭代方法反转循环链表的 Go 语言程序
package main
import "fmt"
type Node struct {
value int
next *Node
}
func nodeAdd(head **Node, value int) {
newNode := &Node{value, nil}
if *head == nil {
*head = newNode
newNode.next = *head
} else {
newNode.next = (*head).next
(*head).next = newNode
*head = newNode
}
}
func printLinkedList(head *Node) {
if head == nil {
fmt.Println("List is empty!")
return
}
fmt.Print(head.value, " ->")
for current := head.next; current != head; current = current.next {
fmt.Print(current.value, " ->")
}
fmt.Println(head.value)
}
func reverseList(head **Node) {
if *head == nil {
return
}
current := (*head).next
prev := *head
for current != *head {
next := current.next
current.next = prev
prev = current
current = next
}
(*head).next = prev
*head = prev
}
func main() {
var head *Node
nodeAdd(&head, 5)
nodeAdd(&head, 3)
nodeAdd(&head, 6)
nodeAdd(&head, 2)
nodeAdd(&head, 4)
fmt.Println("Initial linked list:")
printLinkedList(head)
reverseList(&head)
fmt.Println("Reversed linked list:")
printLinkedList(head)
}
输出
Initial linked list: 4 -> 5 -> 3 -> 6 -> 2 -> 4 Reversed linked list: 2 -> 6 -> 3 -> 5 -> 4 -> 2
方法二
在这个例子中，我们将使用递归方法定义一个 reverseList() 函数，该函数用于反转循环链表。
算法
步骤 1 − 首先，我们需要导入 fmt 包。
步骤 2 − 然后，初始化一个 node 结构体来表示循环链表的元素。每个节点都有一个值和一个指向下一个节点的 next 指针。
步骤 3 − 现在，创建一个 nodeAdd() 函数，该函数将新节点添加到循环链表中。它创建一个具有给定值的新节点，并将其插入到头节点之后。
步骤 4 − 定义 printList() 函数来打印循环链表中所有节点的值。
步骤 5 − 现在，创建一个名为 reverseList() 的函数。它使用递归辅助函数来遍历和反转列表。
步骤 6 − 如果当前节点等于头节点，则更新 next 指针以指向列表的新节点。
步骤 7 − 否则，使用下一个节点作为当前节点、当前节点作为前一个节点以及头节点作为相同节点递归调用该函数。
步骤 8 − 在每次递归调用中，更新当前节点的 next 指针以指向前一个节点。
步骤 9 − 最后，返回初始头节点作为列表的新节点，因为它是在访问和更新的最后一个节点。
步骤 10 − 开始 main() 函数。在 main() 函数中，将几个节点插入循环链表。
步骤 11 − 现在，调用 reverseList() 函数并将第一个非头节点作为当前节点、nil 作为前一个节点以及列表的头节点作为参数传递给函数。
步骤 12 − 此外，使用 fmt.Println() 函数将反转后的循环链表打印到屏幕上。
示例
以下是使用递归方法反转循环链表的 Go 语言程序
package main
import "fmt"
type Node struct {
value int
next *Node
}
func nodeAdd(head *Node, value int) *Node {
newNode := &Node{value: value}
if head == nil {
newNode.next = newNode
} else {
newNode.next = head.next
head.next = newNode
}
return newNode
}
func printList(head *Node) {
if head == nil {
fmt.Println("Empty list")
return
}
fmt.Print(head.value)
current := head.next
for current != head {
fmt.Printf(" -> %d", current.value)
current = current.next
}
fmt.Printf(" -> %d\n", head.value)
}
func reverseList(current, prev, head *Node) *Node {
if current == head {
current.next = prev
head.next = prev
return current
}
next := current.next
current.next = prev
return reverseList(next, current, head)
}
func main() {
var head *Node
head = nodeAdd(head, 5)
head = nodeAdd(head, 3)
head = nodeAdd(head, 2)
head = nodeAdd(head, 4)
head = nodeAdd(head, 1)
fmt.Println("Initial linked list:")
printList(head)
fmt.Println("Reversed linked list:")
reversed := reverseList(head.next, nil, head)
printList(reversed)
}
输出
Initial linked list: 1 -> 5 -> 3 -> 2 -> 4 -> 1 Reversed linked list: 1 -> 4 -> 2 -> 3 -> 5
结论
我们已经成功编译并执行了一个 Go 语言程序，该程序使用递归和迭代方法反转循环链表，并附带两个示例。在第一个示例中，我们使用了迭代方法；在第二个示例中，我们使用了递归方法。生成的已反转循环链表将作为输出打印到控制台。
93 次浏览
