資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究使用遞迴重新排序列表的Go語言程式
連結串列是一種資料結構，由節點集合組成，每個節點包含一個值和指向列表中下一個節點的指標。在這篇Go語言文章中，我們將學習如何使用遞迴和一些輔助函式來重新排序列表。
語法
func reorderList(head *Node) {…}
reorderList() 函式用於使用遞迴重新排序列表。它以指向頭節點的指標作為引數。
演算法
步驟1 − 首先，我們需要匯入 fmt 包。
步驟2 − 現在，建立一個名為 Node 的連結串列單個節點的結構體。它包含兩個成員，一個用於儲存節點的資料值，另一個是用於指向列表中下一個節點的指標。
步驟3 − 現在，建立一個名為 reorderList() 的函式，該函式以連結串列的頭節點作為輸入，並修改列表以重新排序。它使用遞迴來實現此功能。
步驟4 − 檢查連結串列是否為空或只包含一個節點，則無需重新排序。
步驟5 − 然後，使用 findMiddle 輔助函式查詢連結串列的中間位置。它使用雙指標技術。
步驟6 − 接下來，使用 reverselist 輔助函式反轉列表的後半部分。它接受列表後半部分的頭節點，並返回反轉後的列表的頭節點。
步驟7 − 然後，使用 mergeLists 輔助函式合併連結串列的前半部分和反轉後的後半部分。合併後的列表將是重新排序後的列表。
步驟8 − 最後，將輸入連結串列的頭節點更新為重新排序後的列表的頭節點。
步驟9 − 啟動 main() 函式。在 main() 函式內部，向連結串列新增節點。
步驟10 − 現在，呼叫 reorderList() 函式重新排序列表並列印更新後的列表。
步驟11 − 此外，透過呼叫 printList() 函式，在螢幕上列印使用遞迴生成的最終更新的重新排序連結串列。
示例1：使用遞迴重新排序列表的Go語言程式
在這個例子中，我們將定義一個使用遞迴的 reorderList() 函式，用於重新排序單鏈表。
package main
import "fmt"
type Node struct {
Val int
Next *Node
}
func reorderList(head *Node) {
if head == nil || head.Next == nil || head.Next.Next == nil {
return
}
fast, slow := head, head
for fast.Next != nil && fast.Next.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
secondHalf := slow.Next
slow.Next = nil
var prev *Node
for secondHalf != nil {
next := secondHalf.Next
secondHalf.Next = prev
prev = secondHalf
secondHalf = next
}
p1, p2 := head, prev
for p2 != nil {
next1, next2 := p1.Next, p2.Next
p1.Next = p2
p2.Next = next1
p1, p2 = next1, next2
}
}
func printList(head *Node) {
for head != nil {
fmt.Printf("%d ->", head.Val)
head = head.Next
}
fmt.Println("nil")
}
func main() {
head := &Node{Val: 8, Next: &Node{Val: 7, Next: &Node{Val: 3, Next: &Node{Val: 4, Next: nil}}}}
fmt.Println("Initial Ordered list:")
printList(head)
reorderList(head)
fmt.Println("Updated Reordered list:")
printList(head)
}
輸出
Initial Ordered list: 8 -> 7 -> 3 -> 4 -> nil Updated Reordered list: 8 -> 4 -> 7 -> 3 -> nil
示例2
在這個例子中，我們將定義一個使用遞迴的 reorderList() 函式，該函式在輔助函式的幫助下用於重新排序單鏈表。
package main
import "fmt"
type Node struct {
Val int
Next *Node
}
func reorderList(head *Node) {
if head == nil || head.Next == nil {
return
}
var prev *Node
slow, fast := head, head
for fast != nil && fast.Next != nil {
prev = slow
slow = slow.Next
fast = fast.Next.Next
}
prev.Next = nil
secondHalf := reverseList(slow)
mergeLists(head, secondHalf)
}
func reverseList(head *Node) *Node {
if head == nil || head.Next == nil {
return head
}
newHead := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}
func mergeLists(l1, l2 *Node) {
for l1 != nil {
l1Next := l1.Next
l2Next := l2.Next
l1.Next = l2
if l1Next == nil {
break
}
l2.Next = l1Next
l1 = l1Next
l2 = l2Next
}
}
func printList(head *Node) {
for head != nil {
fmt.Printf("%d ->", head.Val)
head = head.Next
}
fmt.Println("nil")
}
func main() {
head := &Node{Val: 5, Next: &Node{Val: 7, Next: &Node{Val: 3, Next: &Node{Val: 2, Next: &Node{Val: 4, Next: nil}}}}}
fmt.Println("Initial Ordered list:")
printList(head)
reorderList(head)
fmt.Println("Updated Reordered list:")
printList(head)
}
輸出
Initial Ordered list: 5 -> 7 -> 3 -> 2 -> 4 -> nil Updated Reordered list: 5 -> 4 -> 7 -> 2 -> 3 -> nil
結論
我們已經成功編譯並執行了一個Go語言程式，使用遞迴方法和兩個示例，結合一些輔助函式來重新排序列表。在第一個示例中，我們使用了遞迴方法；在第二個示例中，我們使用了遞迴方法以及輔助函式。
瀏覽量：156
