前言
在電腦科學中，鍊錶是一種基本的資料結構，它由一系列節點組成，節點透過指標來相互連結。鍊歷可以方便地實現插入和刪除操作，但是存取操作的效能相對較差，因為需要透過遍歷來尋找元素。本文將介紹如何使用Golang實作單鍊錶的倒轉演算法。
單鍊錶的定義
在Golang中，我們可以使用結構體來定義單鍊錶。定義一個結構體Node，表示單鍊錶的節點，其中包含了該節點的值val和它指向下一個節點位置的指標next。
type Node struct {
val int
next *Node
}定義一個head指針，指向鍊錶的頭節點。如果鍊錶為空，head指向nil。
var head *Node = nil
單鍊錶的初始化
在Golang中，我們可以使用new函數來分配一個節點的內存，並傳回該節點的指標。
func newNode(val int) *Node {
return &Node{
val,
nil,
}
}建立一個單鍊錶，可以透過不斷的使用newNode新增節點來實現。以鍊錶1,2,3為例，程式碼如下：
node1 := newNode(1) node2 := newNode(2) node3 := newNode(3) node1.next = node2 node2.next = node3 head = node1
單鍊錶的倒轉
有兩種方法可以實現單鍊錶的倒轉：迭代和遞歸。
方法一：迭代
迭代法的核心思想是遍歷鍊錶，並且把目前節點的指標指向前一個節點，以此達到倒轉的目的。
具體實作過程如下：
Golang實作程式碼如下：
func reverseList1(head *Node) *Node {
var prev *Node = nil
var next *Node = nil
for head != nil {
next = head.next
head.next = prev
prev = head
head = next
}
return prev
}方法二：遞歸
遞歸法的核心思想是先遞歸到鍊錶的末尾，然後再倒序返回已經遍歷的節點。
具體實作過程如下：
Golang實作程式碼如下：
func reverseList2(head *Node) *Node {
if head == nil || head.next == nil {
return head
}
newHead := reverseList2(head.next)
head.next.next = head
head.next = nil
return newHead
}完整的程式碼如下：
package main
import (
"fmt"
)
type Node struct {
val int
next *Node
}
func newNode(val int) *Node {
return &Node{
val,
nil,
}
}
var head *Node
func reverseList1(head *Node) *Node {
var prev *Node = nil
var next *Node = nil
for head != nil {
next = head.next
head.next = prev
prev = head
head = next
}
return prev
}
func reverseList2(head *Node) *Node {
if head == nil || head.next == nil {
return head
}
newHead := reverseList2(head.next)
head.next.next = head
head.next = nil
return newHead
}
func main() {
node1 := newNode(1)
node2 := newNode(2)
node3 := newNode(3)
node1.next = node2
node2.next = node3
head = node1
fmt.Println("原链表：")
for head != nil {
fmt.Printf("%d->", head.val)
head = head.next
}
head = node1
head = reverseList1(head)
fmt.Println("
迭代法倒转后的链表：")
for head != nil {
fmt.Printf("%d->", head.val)
head = head.next
}
head = node1
head = reverseList2(head)
fmt.Println("
递归法倒转后的链表：")
for head != nil {
fmt.Printf("%d->", head.val)
head = head.next
}
}運行結果如下：
原链表： 1->2->3-> 迭代法倒转后的链表： 3->2->1-> 递归法倒转后的链表： 3->2->1->
結語
本文介紹如何使用Golang實作單鍊錶的倒轉，並介紹了兩種不同的實作方法：迭代和遞歸。相信透過本文的學習，大家已經掌握了這兩種方法的核心思想，能夠靈活地應用在實際開發中。
以上是golang單鍊錶倒轉的詳細內容。更多資訊請關注PHP中文網其他相關文章！
