go实现反转链表

Go实现反转链表

简介

在 Go 中实现反转链表需要了解链表的基本概念和 Go 函数的用法。

链表由节点组成，每个节点包含一个数据域和一个指针域，指向下一个节点。而反转链表就是将所有节点的指针指向倒转。实现反转链表的过程，可以使用三个指针。

代码实现

下面是一个基于 Go 语言实现反转链表的示例代码。

type ListNode struct {
    Val int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head

    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }

    return prev
}

代码解释

首先我们声明了一个链表结构体，它包含了一个数据域 Val 和一个指向下一个节点的指针域 Next。

type ListNode struct {
    Val int
    Next *ListNode
}

接着，我们定义了一个名为 reverseList 的函数，它接收一个指向链表开头的指针 head，返回一个指向链表结尾的指针。

func reverseList(head *ListNode) *ListNode {}

我们使用三个指针变量来完成链表的反转。指针 prev 用来保存已反转部分的链表，指针 curr 则用来遍历原链表，而指针 next 则用来保存 curr 的 next 指针。

var prev *ListNode
curr := head

接下来，我们对链表进行遍历。当当前节点 curr 不为 nil 时，取出 curr 的下一个节点 next，将 curr 的 next 指针指向 prev，然后将 prev 指向当前 curr 节点。最后，将 curr 重新赋值为 next，继续遍历下一个节点。

for curr != nil {
    next := curr.Next
    curr.Next = prev
    prev = curr
    curr = next
}

遍历结束后，链表反转完成。最后，我们返回 prev 指向反转后的链表结尾。

return prev

示例说明

下面我们使用以下两个示例测试我们的反转链表代码。

示例1：

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

func main() {
    // 创建测试链表
    l1 := &ListNode{Val: 1}
    l2 := &ListNode{Val: 2}
    l3 := &ListNode{Val: 3}
    l4 := &ListNode{Val: 4}
    l5 := &ListNode{Val: 5}
    l1.Next = l2
    l2.Next = l3
    l3.Next = l4
    l4.Next = l5

    // 反转链表
    result := reverseList(l1)

    // 输出反转后的链表
    for result != nil {
        fmt.Printf("%d -> ", result.Val)
        result = result.Next
    }
    fmt.Println("NULL")
}

我们创建了一个包含 5 个节点的链表，然后将它传入函数 reverseList 中进行反转，最终输出了反转后的链表。

示例2：

输入: NULL

输出: NULL

func main() {
    // 创建空链表
    var l1 *ListNode

    // 反转链表
    result := reverseList(l1)

    // 输出反转后的链表
    if result != nil {
        fmt.Printf("%d -> ", result.Val)
        result = result.Next
    }
    fmt.Println("NULL")
}

我们创建了一个空链表，然后将它传入函数 reverseList 中进行反转，最终输出了 NULL。