Go 常见算法面试题篇(一):反转单链表
xueyuanjun
共 1618字,需浏览 4分钟
· 2021-08-03
上周周末有人和我交流反转单链表的实现代码,正好我也要写常见算法面试题系列,就着这个机会开始这个系列,和数据结构和算法系列并行,以便学以致用。
题目
那就从反转单链表开始吧,这个题目来自《剑指 Offer》这本书,原题如下:
定义一个函数,输入一个单链表的头结点,反转该单链表并输出反转后单链表的头结点。
对于双向链表来说,显然不存在反转的问题,因为它有前驱结点和后驱结点,所以我们限制了条件为单链表。
核心思路
要反转一个单链表并不难,可以参考双向链表的实现,在遍历单链表的过程中,记录当前结点为下一个结点的前驱结点,对于头结点而言,前驱结点为空,然后在遍历到下一个结点时,将上一步设置的前驱结点作为该结点的后驱结点,依次类推,直到遍历到尾结点(后驱结点为空的结点是尾结点),再把尾结点拷贝为反转后单链表的头结点并返回即可:
实现代码
有了以上的思路,我们编写对应的 Go 实现代码如下,在编写过程中,要关注代码鲁棒性,比如链表为空,包含一个结点以及包含多个结点情况如何处理:
package main
import "fmt"
type Node struct {
data interface{}
next *Node
}
// 反转单链表
func (head *Node) reverse() *Node {
// 空链表
if head == nil {
return nil
}
var reverseHead *Node // 反转后单链表的头结点
var preNode *Node
curNode := head
for curNode != nil {
nextNode := curNode.next
if nextNode == nil {
reverseHead = curNode // 尾结点转换为头结点
}
// 反转实现,当前结点的前驱结点变成后驱结点
curNode.next = preNode
// 设置下一个结点的前驱结点
preNode = curNode
curNode = nextNode
}
// 返回反转后的头结点
return reverseHead
}
最后编写一段测试代码验证单链表反转是否成功:
// 遍历单链表
func (head *Node) traverse() {
node := head
for node != nil {
fmt.Printf("%v ", node.data)
node = node.next
}
}
func main() {
first := &Node{data: 1}
second := &Node{data: 2}
third := &Node{data: 3}
first.next = second
second.next = third
head := first
fmt.Print("反转前: ")
head.traverse()
fmt.Println()
newHead := head.reverse()
fmt.Print("反转后: ")
newHead.traverse()
fmt.Println()
}
运行上述代码,打印结果如下,表明单链表反转成功:
评论
Go Heap Profile 怎么了?
Go heap profile 是常常用来检查内存泄露和内存占用大问题的问题的手段,而且非常常用。而且,我们也经常创建两个间隔较长的 heap profile, 获取它们的差值来方便查看内存泄露: Hi, 使用多年的 go pprof 检查内存泄漏的方法居然是错的?! [1]今天,度厂的一位同学提出
GoCN
0
学一学 Spring Boot 3.x
在 Java 后端开发领域,功能强大的 Spring 开源框架不仅是首选,也是事实上的标准。但由于 Spring 存在配置烦琐、部署不易、依赖管理困难等问题,因此基于 Spring 的快速开发框架 Spring Boot 应运而生,它能大大简化 Spring 应用程序的配置和部署过程。2018 年,
小哈学Java
0
聊一聊我最常关注的9个计算机视觉、自动驾驶、AI方向高质量圈子
随着计算机视觉(2D/3D)、SLAM、自动驾驶、AI技术的快速迭代更新,可落地的技术也成为人们争先学习的重点。这使得从业者对于最前沿技术的获取能力变得至关重要。微信公众号便是一个非常有效的前沿信息分享平台。这里给大家推荐9个最常打开的计算机视觉、自动驾驶、SLAM、机器学习和AI方向的优质公众号平
机器学习初学者
0
Go 1.22 的新增功能系列之二:reflect.TypeFor
Go 1.22 的第一个候选版本已经发布,这意味着最终版本即将发布,现在是我在博客中介绍我在这个周期中所做工作的时候了。像往常一样,我的贡献很小,但它们是我的,所以我将从幕后的角度来谈谈它们。首先是reflect.TypeFor。这是整个函数:// TypeFor returns the [Type
GoCN
0
Go早期是如何在Google内部发展起来的
2007年Go诞生于Google,2009年Google正式对外宣布了Go语言的开源!时至今日,距离Go开源已经过去了近15个年头了[1]!Go在Google公司内部究竟是怎样的一个状态呢?前Google员工Yves Junqueira近期撰文从其个人所见所闻谈了Go在Google的历程[2]!这里
GoCN
0
Go 1.22 的新增功能系列之一:cmp.Or
截至撰写本文时,Go 1.22 已经发布几个月了。早就该结束我为 1.22 所做的工作的系列了。抱歉耽搁了这么久,我最近忙于生活事务。如果您错过了我关于reflect.TypeFor(https://blog.carlana.net/post/2024/golang-reflect-type-for
GoCN
1
【送书福利】《Java面试八股文:高频面试题与求职攻略一本通》
先来唠唠最近粉丝面试回来跟我聊天,基本上都提到一个点,在面试过程中八股文占比很高(八股文70%、项目20%、10%算法)除了一些搞算法突出的厂除外。其实现在很多厂八股都是逐渐深入的方式来问,所以大家在学习的过程中,针对一些重点的内容,最好深入去学习,不然还是比较难应对这种追问式的问题。最近刚好从一位
Java后端技术
0
AI论文写作工具和生成器(一)
随着人工智能和大模型的迅猛发展,AI对研究人员和学生提供了极大的写作便利。本文将介绍市面上常用的AI论文写作工具,帮助你提高论文写作效率并遵循学术道德。请仅将AI论文生成器视为辅助参考手段,切勿直接挪用全文。XPaper AlXPaper AI是由点击式创作工具晓语台推出的一款论文写作生成平台,只需
IQ前端
0