golang单链表倒转

2023-05-15 11:05:49 链表 Golang 倒转

前言

在计算机科学中，链表是一种基本的数据结构，它由一系列节点组成，节点通过指针来相互链接。链表可以方便地实现插入和删除操作，但是访问操作的性能相对较差，因为需要通过遍历来查找元素。本文将介绍如何使用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

单链表的倒转

有两种方法可以实现单链表的倒转：迭代和递归。

方法一：迭代

迭代法的核心思想是遍历链表，并把当前节点的指针指向前一个节点，以此达到倒转的目的。

具体实现过程如下：

定义三个指针: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实现单链表的倒转，并介绍了两种不同的实现方法：迭代和递归。相信通过本文的学习，大家已经掌握了这两种方法的核心思想，能够灵活地应用到实际开发中。

以上就是golang单链表倒转的详细内容，更多请关注其它相关文章！

相关文章