前言
在计算机科学中，链表是一种基本的数据结构，它由一系列节点组成，节点通过指针来相互链接。链表可以方便地实现插入和删除操作，但是访问操作的性能相对较差，因为需要通过遍历来查找元素。本文将介绍如何使用Golang实现单链表的倒转算法。
单链表的定义
在Golang中，我们可以使用结构体来定义单链表。定义一个结构体Node，表示单链表的节点，其中包含了该节点的值val和它指向下一个节点位置的指针next。
type Node struct {
val int
next *Node
}定义一个head指针，指向链表的头节点。如果链表为空，head指向nil。
立即学习“go语言免费学习笔记（深入）”；
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
单链表的倒转
有两种方法可以实现单链表的倒转：迭代和递归。
方法一：迭代
迭代法的核心思想是遍历链表，并把当前节点的指针指向前一个节点，以此达到倒转的目的。
具体实现过程如下：
- 定义三个指针:prev, head, next
- 遍历链表，将head的next指针指向prev
- 将prev指针指向head
- 将head指向next
- 重复上述步骤，直到head为空为止
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
}方法二：递归
递归法的核心思想是先递归到链表的末尾，然后再倒序返回已经遍历的节点。
具体实现过程如下：
- 递归到链表末尾
- 将该节点的next指向倒数第二个节点
- 将倒数第二个节点的next指向空
- 重复上述步骤，直到返回原链表的头节点
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实现单链表的倒转，并介绍了两种不同的实现方法：迭代和递归。相信通过本文的学习，大家已经掌握了这两种方法的核心思想，能够灵活地应用到实际开发中。
