链表经典热门考题(下篇)

下篇的难度相较于上篇的难度有所提升，主要还是一以链表为主，更加的锻炼大家的思维能力。
语言：还是采用C语言
下篇共有六道题目，三道牛客，三道力扣
“三人行，必有我师”

返回链表中的倒数第k个结点

链表中的倒数第k个结点

这道题目我写了两种解法。
方法一

先遍历链表，得出链表的长度(假设用变量n表示)，然后先前走n-k，就能找到倒数的第k个结点。

但是如果链表的长度只有5，结果k却等于6，怎么办呢？
这时，我们就要在得出链表的长度之后，加上一个判断，如果k > n的话，直接返回NULL即可。

方法二：快慢指针

最开始让两个指针都指向第一个结点，我们让快指针先走k步，然后快指针走一步，慢指针走一步，最后返回慢指针。

那么循环的判断条件就是，快指针是否为空。

有同志就说为什么这个方法就行了呢？怎么想到的呢？
这个思想的原理其实也很简单，想象一下，如果跑步比赛一开始人家就领先你100米的距离（你俩的速度相同），那么等人家到终点的时候，你是不是还有最后的100米。

链表的分割

链表的分割

这道题目的难度为较难，我们就直接给解题的思路了。
思路其实你知道了之后，也不难，主要是，你能不能想的到这中方法。

因为题目要求不能改变原来的数据顺序，所以我们就不能使用排序之后再返回小于X的链表这种思路了。

我们可以遍历一遍链表，然后将小于X的数据，全部尾插到一起，组成一个新的链表返回，这样既能找到所有小于X的数据，也不会改变它们原来的顺序。

这里因为我使用了头结点，因为有头结点的话，尾插就不必考虑空指针的情况了，所以在结尾处要记得释放一下。

链表的回文

链表的回文

这道题目对时间和空间复杂度都要要求，就极大的限制了我们的做法， 要求我们不能开辟新的空间，并且只能遍历一遍链表。

所以很多同学想到的先找到中间的结点再与第一个结点向后一一比较的思路就不行了，因为时间复杂度超了，大家可以试一下。

这里我们直接采用下面的方法来写。

先通过快慢指针找到中间结点，然后将后半部分的结点逆置（在上篇文章我们已经实现了链表的逆置，不知道的同志可以去看一下上篇的一道题），然后再开始比较。

此时，逆置后完成的链表就是下图中的结构。

第二个结点2还是指向3的，这点值得揣摩。

然后我们就开始比较，相同的话就向后走，然后出现的不相等的情况就直接返回false即可。

如果能走到最后，就说明该链表满足回文结构的要求，返回true即可。

环形链表的判断

接下来的两道题目比较考验的是大家的数学思维能力，直接跟我的思路走就好了，看明白是咋回事之后，记住这个方法也就差不多了。
这两道题目也是比较经典的题目了。

环形链表

这题我们先定义一下快慢指针，还是慢指针走一步，快指针走两步，那么我们知道当快指针走到最后一个结点的时候，慢指针处在中间结点的位置，此时快指针再继续走的话，就会进行到环中，那么当慢指针也进入环中的时候，两个指针的关系就变成了追击问题的模型了。

此时还是快指针走两步，慢指针走一步，两者的速度差为1，肯定就会有相遇的时候了，当快慢指针相等的时候，就返回true。

当我们的循环结束的时候，就代表该链表不是环形链表。
下到题目更有意思。

环形链表的入表点

环形链表2

注意，我们以例一为例，来看一下入表点

这道题目跟上道很相似，就是加了一个条件，求入表点，没有就返回NULL；

有的同志就发懵了，是这tm怎么搞啊，别急，我来点一下睛。
假设我们的两个指针已经相遇了，也就是我们上面一道题目的情况。

此时我们断开slow(或者fast)的next，也就是将slow->next = NULL。
此时环形处就会出现裂口。

那么从第一个结点开始，和从slow->next开始，是不是就是求两个链表的交点那道题目（详细见上篇文章），此时我们就调用一下那道题目的函数即可得到交点（即入口点）的地址。

这道题目还有另外一种解法，先给结论，再来证明

当快慢指针相遇之后，再用一个一个指针指向第一个结点，此时第一个结点距离入口点的距离，和快慢指针相遇点距离入口点的距离相同。
（L == N）

证明如下：

代码：

复制带随机指针的链表

复杂链表的复制


题目的大概意思就是，给你一个链表，该链表的结点不仅仅有一个指针指向下一下结点，每一个结点还存在着一个随机指向的指针random，该指针可以指向链表的任意结点，称为随机指针。
你要做的就是复制一份该链表并返回。

这道题目考的就是怎么复制random这个指针。
步骤一：
拷贝原链表的数据，放在相同数据的后面，如下图所示：

然后根据原链表数据的random指针，将复制的结点的random链接起来。

原数据7的random指向NULL – 该结点的next即是复制的7，复制的7的random也指向NULL
此时走到原数据的13，该结点的random指向7，那么该结点的next即是13，复制的13结点要向指向复制的7结点，只需要原数据的13结点random->next即可找到被复制的7的结点。
以此往复，即可将去全部被复制的结点的random链接起来。

这部分结合代码来看更好

第三步就是将链接好的链表拿下来，就是一个尾插的过程。

最后为了防止传过来的链表是空表，我们最后在复制的链表的尾结点指向空的时候，加上if语句判断即可。


结束结束，饿死了WC！