資料結構
網路
關係資料庫管理系統 (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 次瀏覽
