golang单链表倒转-Golang-PHP中文网

golang单链表倒转

WBOY

发布： 2023-05-15 11:09:08

原创

482人浏览过

前言

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

登录后复制

单链表的倒转

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

方法一：迭代

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

小清论坛 v2.1

asp简单论坛小清论坛是一个以asp+access进行开发的简单论坛源码，要求很低，容易维护。 1、修改系统提示为跳转页面提示。 2、增加小黑屋、用户列表等页面，增加后台对管理员管理。 3、修复后台删人时，同时删除用户头像时出错的问题。 4、修复搜索词会出现乱码的情况。 5、增加后台可以对友情链接、版块进行排序的功能。 6、增加自动生成的二维码扫码功能（暂未有手机版对接）。 7、

208

查看详情

具体实现过程如下：

定义三个指针: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单链表倒转的详细内容，更多请关注php中文网其它相关文章！