啊对了,有很多朋友【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? 课上教的:每个类都有一个构造函数,但是没说 只能有一个 构造函数啊~~太坑了。
那么如果有三个构造函数,应该取哪一个作为默认值在实例化类并创建对象时使用呢?
我们下一期再继续,马上回来。



