栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【日题】关于躺下的数组突然跳起来殴打我这件事(上)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【日题】关于躺下的数组突然跳起来殴打我这件事(上)

啊对了,有很多朋友【bushi】私信告诉我【meiyou】,说为啥我的题目看起来像是C++,事实上给的例子却是Java呢~~~好滴,今天就在节目开始之前回答一下粉丝提问【chedan】。

好吧,还是醒醒吧,我没有粉丝,哈哈哈哈哈哈哈哈哈哈5555555……

在此声明一下,我目前每天做的题,基本都是Java的,可能有极少数Python的解法,那也一定是非常简单的题目。

好了,今天的故事是什么呢?是一个关于“数组到底是不是数组“的故事~~

数组有着非常好的流通性,在很多情况下数组都是作为:上至数据库结构【当然,那个已经算是超级数组了,不算数组了】,下探新手练习题的一种存在。

我们可以在定义完数组、灌完数据以后,想提取哪个元素,就提取哪个元素,按照索引(index)来查找就是了,方便正常的人类进行查找和操作。

但是我们注意到,数组并不是很方便插入数据,在一些涉及系统架构的底层结构数据存储的时候,往往有一种并不是很常见,并不为新人所熟知的结构存在着。

那就是——链表。

好吧好吧,我知道你们一听说这个就要划走看下一篇了,好歹让我把今天的题目放出来给你看一眼。

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

比如:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

再比如:

输入:head = [1,2]
输出:[2,1]

还比如:

输入:head = []
输出:[]

好,那么眼尖的同学、记性好的同学、做题如海的同学已经发现了。

这道题就是传说中 LeetCode 必做的一道题之一——206. 反转链表

首先咱们先来讲一下链表是怎么回事,我之后会单开一篇小文,借由自己的感悟,谈一下对链表的感想,大家一定要捧场哦~~~因为本人比较喜欢用轻松的方式来与人沟通,尽量用一些入门选手能够理解的话语和图解来解释哦~

我们首先要知道链表一些重要的性质 ~_~

1. 链表(Linked List)与数组(List)都是一串数据;

2. 数组(List)可以提供索引来获取数据;但链表只有第一个元素(我们叫节点 Node)可以被获取;

3. 数组各个元素之间没有逻辑上的关联;链表的相邻节点(node)有关联,“当前节点”(cerrent node)保存着“下一个节点”(next node)的内存地址;

4. 由于以上三点性质,导致我们如果想要获取一个链表,只能获得它的“头结点”(head),它的头结点就是链表本身(中国本身就是百年未有之大变局,句式一样,夹带私货hehe),一旦获得头结点,就可以把链表从内存海洋中一把全拉出来~

以上的几点,这是一个非常肤浅、非常外行、甚至有所错误的解释,只能用作入门理解,切不可当做教条。

如果需要专业解释请移步隔壁各种大佬开的论坛和博客,在我这里,只是力求让更多的小伙伴有一个大概的理解,这样,即便 悟性不好 的同学【meiyou】,也能有一个基本的认识,方便大家以后展开联想。

为了完整的模拟这道题,我不仅写了题中要求的“翻转链表”的部分,还写了题目本身的验证代码逻辑,

有需求的可以关注微信公众号“不勤劳的老蜜蜂”,回复“链表”索取哟~

那我们来说一下这个题目吧~~~终于到关键部分了。

看完题目,如果让大家用数组来做这道题,那一定是异常简单的:

获取数组长度,遍历整个数组,把每个元素的索引都倒着引用进一个新数组就好了嘛!

没错,这样的话,大概也就最多 6 行代码,就结束战斗了。

· 数组的性质:

{ “数据 0”,“数据 1”,“数据 2”,...,“数据 n” };

· 链表的基本属性大概是:

{ ( “数据 A” + “B节点的内存地址” ),( “数据 B” + “C节点的内存地址” ),... ( “数据 N” + null )}

可以看到,链表最少要由两部分组成:“数据”和“下一节点地址”。

“数据”好说,如果我想存储一个 int 类型的数据,就传入一个数字就好了。但是“下一节点地址”如何存储呢?

涉及到“类的自引用”,即以这个“下一节点地址”这个变量本身所属的类来定义变量自己。

说起来有点绕,如下图所示:

这是一个定义“节点”(node)的类(class),我们可以看到有两个参数,

一个是—— int val;  这个好理解,就是我们上面提到的“数据”,在这里是一个 int 值,

一个是—— ListNode next;     这个是一个 ListNode 类型的参数 next,next 指代的就是“下一个节点的地址”。

那么 “ListNode” 是个什么类型呢?不,这并不是基本库中的某个类型,如果我们注意一下这个类的名称,就会发现,这个类名就叫“ListNode”……

也就是说,这个类里面的某个参数的类型,就是这个类本身~~

很多刚学 Java 的同学马上就蒙蔽了。WC ?这是什么意思?

没关系,你只要把这个现象背下来就行了。

啊不对,我的意思是,由于 Java 中没有明确的指针 ,要用这种类自引用的方式,连锁创建对象,让对象能够存储下一个对象的内存地址,从而产生联系,从而产生——

链表。

图中我们还能看到有 三个 构造函数:ListNode(),ListNode(int val), ListNode(int val, ListNode next)。

不要怀疑,你没看错,就是三个构造函数,这时候新入坑的同学们又蒙蔽了——

WC? 课上教的:每个类都有一个构造函数,但是没说 只能有一个 构造函数啊~~太坑了。

那么如果有三个构造函数,应该取哪一个作为默认值在实例化类并创建对象时使用呢?

我们下一期再继续,马上回来。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/930907.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号