数据结构与算法|数据结构学习笔记 1-1链表概述及LeetCode真题图解（Java） leetcode|面试|图解法|数据结构

喜欢该类型文章可以给博主点个关注，博主会持续输出此类型的文章，知识点很全面，再加上LeetCode的真题练习，每一个LeetCode题解我都写了注释，比较适合新手入门数据结构与算法，后续也会更新进阶的文章。

1-1 链表(List)及经典问题链表基础知识

数据结构与算法|数据结构学习笔记 1-1链表概述及LeetCode真题图解（Java）

文章图片

链表的典型应用场景

文章图片

现在我们有这样一个需求：现在这个4GB的内存是一个连续的存储空间，接下来我们是要在4GB的内存空间划分出来1GB的存储空间，如图：

文章图片

malloc函数是c语言里的内容，就好比java里的new；作用相同的，就是开辟存储空间。
可以想象成我找了一个1GB大小的数组，虽然有点夸张，只是举例。
经过我这样的申请空间之后，我们把我们的整个数据切分了，原本是好好的一整块数组，变成两块了，一个是2GB的碎片，一个是1GB的碎片，如图：

文章图片

那我们接下来在程序里申请空间的话，我们如何去管理这个内存碎片？
操作系统底层里面，把两个内存碎片用链表给他窜起来，我们可以通过2GB找到1GB的碎片，这样就不至于说我们内存里面出现碎片丢失，有一片存储空间找不到的情况；这是简单的一个应用。

文章图片

现在只是简单拿出来了解一下，后续会对这个LRU缓存淘汰算法进行详细的讲解。
什么是LRU？你可以理解为冰箱里有好多菜，我周一买了些菜，周二买了些菜，周日也买了些菜，但我们最后发现冰箱里放不下了，这时候我们新买的菜也不能不放进冰箱里，所以这时我们只能在冰箱里挑出一些菜给它扔掉，这时候我们会扔哪些菜呢？答案肯定是放的最久的菜，因为是最容易坏的。

文章图片

那我们如何区分哪个最久呢？我们可以用链表给它链起来，这样我们就知道，哪个菜是最开始就放进冰箱里的，我们可以优先将它淘汰掉，并放入我们新的菜，就好比将图片中的数据1删掉，存入新的数据5，再想填入新的数据，删掉数据2，以此类推。

文章图片

假设数据3是我们非常想吃的菜，但按照顺序即将被淘汰掉，我们可以把数据3拿出来，放在最后，更新一下它的优先级，这样的话数据3的优先级就高于数据4，我们删除数据2之后，会删除数据4；这是链表常用的一个实现方式。

文章图片

链表使用的场景还是非常多的。
链表与数组的结构性能对比 【数据结构与算法|数据结构学习笔记 1-1链表概述及LeetCode真题图解（Java）】数组的存储是连续、聚合的
链表的存储是离散的，我们通过抽象的指针域概念连接了起来
数组是一段连续的存储空间，支持数据随机访问，我们想找到哪个数据就可以立刻找到；但我们假设有一个100内存的数组，我想对这个数组进行扩容的话，我可能需要申请一个200内存的数组，再把100内存数组的所有数据原封不动的搬过去，这样我们才能得到一个200内存的数组。
链表是非连续的，扩容非常简单，找一个结点，就可以实现插入或者删除；但我们如果访问数据的话，就只能随机的访问，它不能按顺序进行访问；
这是我们从数据结构层面进行对比。
那我们从硬件层面考虑呢？
CPU读取优化

文章图片

读取数组时，假设我想读取数组的第100个数，我可以直接找到数据并将它拿出来，但真正计算机实现里面，我们真的是只把100这一个数据从内存拿到cpu里面吗？其实不是的，内存的内容导到cpu里，这叫做上下文切换。这种数据之间的读取是非常耗时的，所以说cpu不会大材小用的，你想读一个东西，我就只老老实实的读一个吗？cpu不是这样的，cpu很不老实，在我们当前节点前后，分别多读取一段内存空间，具体数据各个硬件不一样，当我们读取100的时候，cpu很多余的将100前后的x个空间都拿出来，它具体读取的内容是x+1+x，虽然你只想读取一个，但是cpu会读取2x+1个数。

文章图片

cpu为什么会这么做？正是因为数组的连续的，如果我想读取一个数的话，那么我读取前面或者后面这个数的概率会大一点，所以它会进行一个多余的操作，但这个操作也不算是多余，它读取一个数据，和再读取这个数据前后的数据，如果时间消耗几乎是一样的话，cpu为什么不多读一点呢？这就是我们cpu层面上的缓存优化。
那对于链表来说，可以用这种优化吗？答案肯定是不能的。因为链表的存储是非常随机的，在内存里一个在东面，一个在西面，当你cpu想读当前这一个链表结点时，它不知道你前面的结点和后面的结点都在哪里，所以说链表有很大的一个缺点，它没有办法运用在我们的cpu缓存优化；对应到我们的工程实现里面，这两个的差距是非常非常大的。
LeetCode真题经典面试题—链表的访问 LeetCode141.环形链表
难度：easy
判断链表是否有环
经典的快慢指针编程思想但是我们从初学者的角度来看是不会想到用快慢指针的
哈希表

最朴素的思想肯定是这种哈希的形式，我们只需要依次遍历整个链表，并创建一个哈希表来存储遍历过的结点。
遍历每一个结点，然后存入哈希表；在存入哈希表之前，先判断哈希表中是否存在该结点。
如果不存在，则存入哈希表；如果已存在，说明遍历到了重复结点，链表有环。

先来看无环的情况：

文章图片

有环情况：

文章图片

这个也是大部分人第一次遇到这种题的思路；大家在面试的时候，可以先写出这种最暴力的方式，然后再去优化，不要一直想着怎么去优化然后连最简单的方式都不写，要不然面试官会以为你连最简单的方式都不会。

总结
我们只需要遍历这个链表，在遍历过程中记录我们遍历的每个结点。
如果遇到next结点为null的结点，说明没有环。
如果遇到我们以前遍历过的结点，说明有环。

但是这种方式是不是有点复杂，我需要开辟一个额外的存储空间来存储每一个链表结点的地址，我们有更优化的方法吗？
题中有一段话：

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

快慢指针
也就是说你不要动态的去申请内存空间，那我们如何不借助哈希表来实现这个题呢？那就是我们刚才提到的快慢指针。
我们定义两个指针，p是慢指针(用红色标记)，q是快指针(用黄色标记)，每次让p结点走一步，q结点走两步。

文章图片

无环：

文章图片

当快指针的next结点为null，或者快指针本身结点为null时，说明该链表没有环，遍历结束。
我们再来看一下有环的情况：

如果链表有环，那么快慢指针一定会相遇，指向同一个结点，当指向同一个结点时，遍历结束。
LeetCode题解：两种方法代码实现
LeetCode142.环形链表II
难度：mid
141是判断是否有环，142是求环的起点。
最简单的方法肯定还是利用哈希表来判断，这里不过多赘述，我们直接上快慢指针。

文章图片

设p走了a的距离，同时q走了2a的距离，此时p处在环的起点，q在环里，设q距离p的距离为x。

文章图片

由于q与p之间的距离为x，所以当p再走x步时，q走了2x步，此时p，q两点相遇；所以相遇点离我们环起点的位置肯定是x。
链表环的总长为a+x，当我们拿到x的长度时，我们也得到了a的长度，此a的长度跟p第一次走到环的起点a的长度是一样的。
此时我们可以将p重新指向头结点，p，q同时走a步，即再次相遇，此相遇位置即为环的起点。

文章图片

重新分析一下整体过程：先看浅蓝色的线，p先走了a步，q走了2a步，此时p在环的起点，q在环里，设环的总长为a+x，看红色的线，先看下面，此时q距离p的距离即为x，再看上面，当p再走x步时，q走2x步，p，q两点相遇，此时相遇点距离起点的距离为x，看绿色的线，从而剩下的距离即为环的总长减去x，(a+x)-x=a，所以此时，我们可以将p指向头结点，p和q同时走a步，即p和q再次相遇，此时即为环的起点。

文章图片

LeetCode题解：两种方法代码实现
经典面试题—链表的反转 LeetCode206.反转链表
难度：easy

文章图片

迭代实现
双指针扫描
这个链表反转其实很像如何交换两个变量的值，我们需要借助另一个变量来实现。
定义指针pre，pre指向null。
定义指针cur，cur指向我们的头结点。
定义指针next，next指向cur所指向结点的下一个结点。

文章图片

首先，我们先将cur指针所指向的结点指向pre指针所指向的结点

文章图片

然后移动指针pre到指针cur所在的位置

文章图片

移动cur到next所在的位置

文章图片

将我们的next指针指向cur指针所指向结点的下一个结点

文章图片

此时我们就完成了第一个结点的反转，1指向了null。
我们继续刚才的操作，将2反转。

文章图片

将剩下的反转。

文章图片

当cur指针指向null的时候，我们就完成了整个链表的反转。

文章图片

递归实现
我们可以借助系统栈来实现，入栈的顺序是1->2->3->4，但我们弹出栈的顺序为4->3->2->1。

文章图片

递归实现对于新手比较难理解，后续到栈的部分会对这里有着更好的理解。
可以根据这张图看代码。

文章图片

LeetCode题解：两种方法代码实现
递归方法也可以看一下这个人的题解，清晰易懂。
LeetCode92.反转链表II
难度：mid
反转给定区间的链表。
首先我们定义一个虚拟头结点，起名叫做hair，它指向我们的真实头结点，它在链表里有一个专有名词：哨兵结点。
为什么要定义一个这样的结点？其实这个东西很简单，它相当于在头结点上面加了一个边界条件，来防止一些边界特判，
假如我们要反转的是1->2->3，那我们反转完之后就是3->2->1->4->5->null，按照我们之前的编程经验来看，我们首先定义一个int p = head，然后再对p进行操作，最后返回的就是head，通常不对head进行操作，但对于这种情况，我们还可以直接返回head吗？head指向的是1，我们最终的链表就只剩1->4->5->null，前面的数被丢掉了；所以这时我们在最前面加入一个哨兵结点，就可以防止这种边缘特判，否则我们就要反转一次判断一下谁是头结点，把头结点记录一下，然后再反转再记录，会很麻烦，而且还加了很多特判。

文章图片

哨兵结点没有什么实际的意义，它不参与我们链表中的活动，你可以把它想象为空，或者里面存的值是-1
但它的任务只有一个，快速找到头结点。

先将hair指向头结点
定义一个指针pre指向hair
定义一个cur指向pre指针所指向结点的下一个结点
让我们的pre指针和cur指针同时向后移动，直到我们找到了第left个结点，也就是题中的2。

文章图片

双指针-头插法
我们可以先将中间的3删除然后插入到1和2之间此时的链表是这样的

文章图片

那么同理，cur指向的还是2，pre指向的还是1，所以我们也可以很轻易的将4删除，插入到1和3之间
此时链表已经达到了题中的反转要求

文章图片

但是单向链表我们想要删除一个结点，我们必须通过它的上一个结点，在插入的过程中，我们应该注意什么？
一个链表1->2，我们想将3插入到1和2之间，我只可以通过1才可以找到2，因为1的下一个结点就是2，我们把1叫做A，把3叫做B，首先让B结点的下一个结点指向A结点的下一个结点，也就是B.next = A.next，如图

文章图片

这么做的目的就是防止1结点和2结点之间断开，而找不到2结点了，这样我们就可以放心大胆的让A的下一个结点指向B，也就是A.next = B，如图

文章图片

这样3就插入进去了，这就是一个头插法的过程，所以本题我们就可以用这个方法来解决。
我们的核心思路就是将cur后面的结点插入到pre后面。
递归
递归还是比较难理解，由于博主也还是初学者，怕我讲的不到位，所以直接给大家看代码吧。
LeetCode题解：两种方法代码实现
经典面试题—链表的结点删除 LeetCode19.删除链表的倒数第N个结点
难度：mid
我们想删除一个结点，那就一定需要这个结点前面的结点。
假如我们想删除b，我们可以使a不指向b而指向c，这样就完成了删除，之后要将b释放掉，代码就是a.next = a.next.next
那我们该如何找到a呢？

文章图片

双重遍历计算链表长度
删除链表倒数第N个结点，也就是删除链表第Length - N 结点的下一个结点。

文章图片

我们需要先遍历链表，求出Length的长度，然后将4删除。

文章图片

题中有一段话：

进阶：你能尝试使用一趟扫描实现吗？

我们按上述方法是扫描了两遍，才可以删除结点，我们如何只扫描一遍就完成删除操作呢？
双指针
我们还是需要我们的老朋友，哨兵结点。
同样也是双指针扫描，快慢指针，p指向hair，q指向head，先让q走n步，此时p和q同时走，当q走到null时，p必定指向的是待删除结点的前一个结点。

文章图片

图是力扣程序员吴师兄的。
LeetCode题解：两种方法代码实现
LeetCode83.删除排序链表中的重复元素
难度：easy
其实还是挺简单的，毕竟是升序排列，也就是说重复元素必定是挨在一起的，我们可以用指针指向的val值跟下一个结点的val值进行对比，如果相同，则直接指向相同结点的下一结点，如果不同，指针往下移。

文章图片

LeetCode题解：代码实现
总结

链表这个数据结构看似简单，没有过多的条件，但它的题都非常有意思，它不涉及一些数据结构算法的思维，但是它每一题的解法都特别巧妙，可以把链表题当成智力测试题，脑筋急转弯，第一次上手那种环形链表，谁能想到用快慢指针呢？这个在面试当中其实是一样的，你不会这个东西你肯定就一直不会，我们如果在面试如果遇到了这种题，在面试的时候也很难再想出来，如果你面试之前做过了这些东西，那么你面试的时候也能大概率的想出来。