【数据结构】链表专题3

前言

本篇博客我们继续来讨论链表专题，今天的链表算法题是经典中的经典

💓 个人主页：小张同学zkf

⏩ 文章专栏：数据结构

若有问题评论区见📝

🎉欢迎大家点赞👍收藏⭐文章

1.判断链表是否有环

2.返回入环的第一个节点

3.随机链表的复制

1.判断链表是否有环

这道题链表尾指针很有可能指向链表中任何一个节点，所以是带环的意思，当然尾指针很有可能指向他自己

所以我们分析一下，该怎么判断带有环，有些人直接说我就判断是否和我原来的值相等，相等的话就是代表有环，但这种情况不能确保一定有环，因为即使我没进环也有可能值相等，所以这个行不通，所以我们要判断的话还得需要快慢指针，若快指针追上慢指针代表这链表有环，为什么快指针追上慢指针就会带有环那？

我们来画图分析一下

slow和fast最初都在头结点，我们让fast一次走两步，slow一次走一步，假如没换那么fast或fast->next就会指向空，假如有环，那么fast先进环，slow后进环，若fast追上slow就证明了这个链表就带有环

代码如下

这道题曾经被一个面试官提出新的问题

为什么一定会相遇，有没有可能会错过，永远追不上？

我们先来看第一个问题，我们假设slow进环后与fast距离为N, 环的长度是C

那么fast追击slow的过程距离变化如下：

N为偶数 N为奇数

N N

N-2 N-2

N-4 N-4

…… ……

4 3

2 1

0 -1

可以看出N若为偶数追上了，若N为奇数，则代表fast错过了，需要新的一轮追击，此刻他们之间的距离就变成了C-1，继续追击，我们根据第一轮追击可以得知，C-1是偶数的话代表第二轮追上了，C-1还是奇数的话，又错了一位，距离又变成了C-1，C-1既然是奇数，那就代表永远追不上了

所以追不上的条件前提是，第二轮的C-1是奇数，第一轮的N是奇数，但我们想想这两个条件会不会同时存在

这里我们就需要用到数学列等式的思维来判断两个条件是否可以同时存在

我们假设进环之前的距离是L

那么slow刚进环时，slow走过的距离是L，此刻我们假设fast走了x圈，那fast走过的距离就是L+x*C+C-N

fast的距离是slow的三倍

那么就有了等式

3L=L+x*C+C-N

换算为：2*L=（x+1)*C-N

偶数=（x+1)*偶数-奇数

我们根据数学运算法则中 ,N是奇数时，C必须是奇数，才能使等式成立，N是偶数时，C必须也是偶数，才能使等式成立。

所以，当N是奇数时，C为奇数，C-1为偶数，所以C-1不可能为奇数，所以不可能永远追不上，肯定相遇。

结论：一定能追上

N是偶数第一轮就追上了

N是奇数第一轮追不上，第二轮就追上了

2.返回入环的第一个节点

上面那道题是判断是否有环，这道题就是若有环，返回环的第一个节点，所以我们还是需要用到快慢指针，我们画图表示

如图，这里其实有个非常巧妙的方法，我们让慢指针一次走一步，快指针一次走两步，直到环里相遇，再创建两个指针，一个从头开始走，另一个从快慢指针相遇的地方开始走，俩指针一次走一步，这俩指针若相遇，则相遇的点必定是进环的首节点

代码如下

可是为什么那？

我们还是用数学的方法来证明一下

我们假设，环之前的距离是L，环的长度为C，相遇点与入环点的距离为N，在慢指针进入环点时，快指针走了x圈

那么相遇时，slow走的距离是L+N

fast走的距离是L+x*C+N

fast走的路程是slow两倍

那么就有了等式

2*（L+N）=L+x*C+N

最后换算成L=（x-1）*C+C-N

假如x=1，那么L=C-N，正好是相遇点到入环首节点的距离与入环之前的距离相等，那么此时在头结点与相遇节点创建俩指针同时走，正好相遇在入环首节点，证实了我们上面的代码想法，但有人会想，你这里假设为1呀，我让它不为一，不唯一的话，相当于在相遇节点的指针多走了几圈C，最后还是在入环首节点相遇。

3.随机链表的复制

这道题链表每个节点里多了个指针指向随机节点，也有可能指向空，然后我们要深拷贝一份（深拷贝意思就是把指针指向对应的值对应关系也要在新拷贝的链表中实现），有人说我直接遍历然后拷贝不就行了，硬拷贝是可以的，但是有个问题，随机指针（random）指向的值如何在新链表中实现，有人说我在新链表里继续找就行呀，但是我们仔细想一下，我们链表里值有可能有时相等，所以如果你先拷贝过去，然后再去找对应的值，可能找到的值不是原链表对应的值，而是值相等的那个位置的节点。