1-1 链表(List)及经典问题

链表基础知识

链表的典型应用场景

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

malloc函数是c语言里的内容，就好比java里的new；作用相同的，就是开辟存储空间。

可以想象成我找了一个1GB大小的数组，虽然有点夸张，只是举例。

经过我这样的申请空间之后，我们把我们的整个数据切分了，原本是好好的一整块数组，变成两块了，一个是2GB的碎片，一个是1GB的碎片，如图：

那我们接下来在程序里申请空间的话，我们如何去管理这个内存碎片？

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

现在只是简单拿出来了解一下，后续会对这个LRU缓存淘汰算法进行详细的讲解。

什么是LRU？你可以理解为冰箱里有好多菜，我周一买了些菜，周二买了些菜，周日也买了些菜，但我们最后发现冰箱里放不下了，这时候我们新买的菜也不能不放进冰箱里，所以这时我们只能在冰箱里挑出一些菜给它扔掉，这时候我们会扔哪些菜呢？答案肯定是放的最久的菜，因为是最容易坏的。

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

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

链表使用的场景还是非常多的。

链表与数组的结构性能对比

数组的存储是连续、聚合的

链表的存储是离散的，我们通过抽象的指针域概念连接了起来

数组是一段连续的存储空间，支持数据随机访问，我们想找到哪个数据就可以立刻找到；但我们假设有一个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题解：代码实现

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