【挑战剑指offer】系列03:逆序打印单链表

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。

1. 【逆序打印单链表】原始题目

算法原题链接:https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&tPage=1&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

原题目描述:

输入一个单链表,按链表值从尾到头的顺序返回一个ArrayList。

单链表的简单设计

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

最先想到的办法:栈

其实jdk提供的工具类也可以做到

到此为止,原题目已经解答完毕。

但是,我们说这个系列不能仅仅局限于解决原始问题,更要手动加大难度,创造更多思路和方案。所以,接下来:

2. 加大原题难度:不允许使用额外的集合、工具

递归存储

使用递归的方式虽然没有显式扩展额外空间,但在内存中创建了递归方法区(递归本来也是栈结构),所以仍然会比较消耗性能。

利用三指针进行原地翻转

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

优秀程序员写代码一定会用的 11 条经验!

我已经写了20年代码了,在此期间曾与17个团队共事过,使用不同的语言做过数百个项目。

9120
来自专栏Golang语言社区

麻将游戏的听牌算法

测试测试!!~~~~这两周都是在测试各种BUG,没事情的时候自己在网上学学新知识,也为下个月的游戏改版预热。最近呢我也开始了我的shader之旅,估计也是这充满...

548160
来自专栏企鹅号快讯

为什么说Kotlin的可读性比Java好?

作者|小创 编辑|覃云 不久之前,我看了一篇文章,大意是 Kotlin 与 Java 之间的对比,像这种文章,我一般是直接忽略的,但是那天我还是打开了,然后就看...

34850
来自专栏小蠢驴iOS专题

Masonry拓展-链式编程 & 函数式编程

14840
来自专栏liulun

Nim教程【三】

这是国内第一个关于Nim的系列教程 (至少我百度和必应是没有找到类似的教程) 先说废话 有人说 Golang的编译器/工具...

21190
来自专栏Java技术栈

告别狗屎代码,请记住这 11 条编码秘诀!

我已经写了20年代码了,在此期间曾与17个团队共事过,使用不同的语言做过数百个项目。

15110
来自专栏nimomeng的自我进阶

探索命名之美(一)

很多新码农在工作中总会被老鸟批评程序命名的陋习,我也被批评过很多次。痛定思过,我决定要研究应该怎么命名,为什么要给函数一个好的命名很难,应该怎么样给函数命名。

18430
来自专栏程序员的SOD蜜

“法天象而应四时”--茶话软件开发之“抽象”(2)--过程的抽象:函数

本想写这样的一个系列的,无奈一直没有时间,没想到网上已经有人写了类似的文章,说明了我原来的观点: 函数既是过程的抽象! 当然,函数的抽象意义远非如此简单,这里先...

21390
来自专栏张泽旭的专栏

回溯法解决八人过河问题

一家六口,一个爸爸,一个妈妈,俩儿子,俩女儿,还有一个警察,一个坏蛋,过一条河,爸爸不在妈妈伤害儿子,妈妈不在爸爸伤害女儿,警察不在坏蛋伤害一家六口,只有妈妈爸...

9620
来自专栏C语言C++游戏编程

「C语言」编程学习—控制语句goto语句解析!

C语言共有9种控制语句:if/else,for,while,do-while,switch/case,break,continue,return,goto。

14930

扫码关注云+社区

领取腾讯云代金券