文档章节

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

LinkedBear
 LinkedBear
发布于 09/21 08:11
字数 412
阅读 8
收藏 5
JDK

本系列的算法原题来自于“牛客网-剑指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. 加大原题难度:不允许使用额外的集合、工具

递归存储

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

利用三指针进行原地翻转

© 著作权归作者所有

共有 人打赏支持
LinkedBear
粉丝 19
博文 49
码字总数 56178
作品 0
济南
程序员
面试:用 Java 逆序打印链表

面试:用 Java 逆序打印链表 昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 关键字,不少朋友问我,到底为啥要加 这个关键字呀,而它,到底又有什么神奇的作...

nanchen2251
07/03
0
0
[算法总结] 一文搞懂面试链表题

本文首发于我的个人博客:尾尾部落 链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。 1. 在 O(1) 时间删除链表节点 题目描述:给定单向链表的...

繁著
08/28
0
0
剑指Offer_6_从尾到头打印链表

题目描述 输入应该链表的头节点 , 从尾到头反过来打印出每个节点的值。链表定义如下 : 1 typedef struct ListNode2 {3 int m_nKey ;4 ListNode * m_pNext ;5 }ListNode;   分析:     ...

奶berber
2017/12/05
0
0
Java实现链表面试题

本文包含链表的以下内容:   1、单链表的创建和遍历   2、求单链表中节点的个数   3、查找单链表中的倒数第k个结点(剑指offer,题15)   4、查找单链表中的中间结点   5、合并两个...

火力全開
2016/10/09
13
0
单链表复制早已难不到你,但若我们再加个指针...

面试 18:复杂链表的复制(剑指 Offer 第 26 题) 在上一篇推文中,我们留下的习题是来自《剑指 Offer》 的面试题 26:复杂链表的复制。 请实现复杂链表的复制,在复杂链表中,每个结点除了 ...

南尘
08/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 到底谁是小公猫……

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子:分享Trivium的单曲《Throes Of Perdition》 《Throes Of Perdition》- Trivium 手机党少年们想听歌,请使劲儿戳(这里) @小鱼丁:...

小小编辑
30分钟前
23
1
基础选择器

注意:本教程参考自网上流传的李兴华老师的jquery开发框架视频,但是苦于没有相应的配套笔记,由我本人做了相应的整理. 本次学习的内容 学习jquery提供的各种选择器的使用,掌握了jquery选择...

江戸川
36分钟前
1
0
Spring中static变量不能@value注入的原因

今天本想使用@Value的方式使类中的变量获得yml文件中的配置值,然而一直失败,获得的一直为null。 类似于这样写的。 public class RedisShardedPool { private static ShardedJedisPool pool...

钟然千落
今天
2
0
CentOS7防火墙firewalld操作

firewalld Linux上新用的防火墙软件,跟iptables差不多的工具。 firewall-cmd 是 firewalld 的字符界面管理工具,firewalld是CentOS7的一大特性,最大的好处有两个:支持动态更新,不用重启服...

dingdayu
今天
1
0
关于组件化的最初步

一个工程可能会有多个版本,有国际版、国内版、还有针对各种不同的渠道化的打包版本、这个属于我们日常经常见到的打包差异化版本需求。 而对于工程的开发,比如以前的公司,分成了有三大块业...

DannyCoder
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部