golang单链表倒转

在Golang中，链表是一种常见的数据结构，用于存储和操作一系列的数据。链表由一个个节点组成，每个节点包含数据项和指向下一个节点的指针。单链表是最简单的一种链表结构，它只能从头节点开始依次访问每个节点。本文将介绍如何使用Golang对单链表进行倒转。

准备工作

在开始之前，我们需要首先创建一个单链表结构体和一些基本的操作函数。我们使用Golang的指针来实现链表的节点指针和倒转操作，以提高效率。

首先，我们定义链表节点的结构体：

type ListNode struct {
    Val  int
    Next *ListNode
}

接下来，我们定义一些常用的链表操作函数，例如创建链表、插入节点和打印链表等：

// 创建一个新的链表
func NewList() *ListNode {
    return &ListNode{}
}

// 向链表末尾插入一个节点
func (head *ListNode) Insert(val int) {
    for head.Next != nil {
        head = head.Next
    }
    head.Next = &ListNode{val, nil}
}

// 打印链表所有节点的值
func (head *ListNode) Print() {
    for head.Next != nil {
        fmt.Printf("%d ", head.Next.Val)
        head = head.Next
    }
    fmt.Println()
}

递归方法倒转单链表

递归是一种非常简洁的方法来倒转单链表。我们可以使用递归函数将链表的每个节点指向前一个节点，直到达到链表末尾。

func ReverseListRecursion(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    newHead := ReverseListRecursion(head.Next)
    head.Next.Next = head
    head.Next = nil
    
    return newHead
}

使用递归方法倒转链表时，需要注意终止条件，即当链表为空或只有一个节点时直接返回。在递归过程中，我们将链表后面的节点倒转后，将当前节点的Next指针指向前一个节点，并将当前节点的Next指针置为nil。最后，返回新的头节点。

迭代方法倒转单链表

迭代是另一种常用的方法来倒转单链表。我们可以使用三个指针prev、curr和next，分别指向前一个节点、当前节点和下一个节点。通过不断更新这三个指针的指向，实现链表的倒转。

func ReverseListIteration(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    
    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    
    return prev
}

在迭代过程中，我们先将当前节点的Next指针保存到临时变量next中，以便后续更新curr指针。然后，将当前节点的Next指针指向前一个节点，然后将prev和curr指针分别往后移动一个节点。

测试示例

现在，我们使用上面定义的链表操作函数创建一个链表并进行倒转操作。

func main() {
    list := NewList()
    list.Insert(1)
    list.Insert(2)
    list.Insert(3)
    list.Insert(4)
    list.Insert(5)
    list.Print() // 打印原始链表：1 2 3 4 5

    newHead := ReverseListRecursion(list.Next)
    newHead.Print() // 打印递归方法倒转后的链表：5 4 3 2 1

    newHead = ReverseListIteration(newHead)
    newHead.Print() // 打印迭代方法倒转后的链表：1 2 3 4 5
}

运行上述代码，我们可以看到原始链表、递归方法倒转后的链表和迭代方法倒转后的链表。

至此，我们已经学习了如何使用Golang对单链表进行倒转。递归和迭代方法都是常用的处理链表问题的技巧，掌握它们将有助于我们更好地理解并解决其他链表相关的算法问题。