今天我们来看两道力扣的OJ题:环形链表与环形链表II
首先,先来认识一下什么是环形链表。环形链表的结构有好几种,比如下面几种都是环形链表
接下来,我们首先来看一下 环形链表I
题目:141. 环形链表
给你一个链表的头节点
head
,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪
next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数pos
来表示链表尾连接到链表中的位置如果链表中存在环 ,则返回
true
。 否则,返回false
思路:
使用快慢指针fast 和 slow
fast追上slow就是带环,fast走到空,就是不带环
知道了使用快慢指针的方法,接下来的问题才是关键
1.一定可以追上吗? 会不会追不上
2.slow走1步,fast走3步能够追上吗?
3.slow走1步,fast走4/5/6/...情况又如何呢?
看到这几个问题,想必小伙伴们也已经意识到:这道题的难点不在于编程,而是数学的逻辑上
我们先来看第一个,也就是常规的快慢指针,slow走1步,fast走2步 一定可以追上吗?
我们下面来分析一下:fast先进环,过一会,slow也进环,此时开始追击。假设此时fast与slow之间的距离为N,那么每追击一次,fast与slow的距离就会缩小一步
图示如下:
下面是fast与slow的距离变化,当距离为0时,也就意味着追上了
所以根据我们的分析,上面提出的第一个问题:
slow走1步,fast走2步 一定可以追上吗? 答案是一定可以追上的
知道了可以追上,我们就根据这个先把 判断链表是否带环 这个问题做一下吧
代码如下:
bool hasCycle(struct ListNode *head)
{
struct ListNode *slow = head;
struct ListNode *fast = head;
while(fast && fast->next)//2个条件分别对应链表个数的奇偶性2种情况
{
slow = slow ->next;//slow走一步
fast = fast->next->next;//fast走两步
if(slow==fast)//追上了
return true;
}
return false;//没追上
}
然后就过了:
不过,接下来我们不妨再来分析一下slow走一步,fast走三步的情况 即上面提出的第2个问题
一起 来看一下吧~
fast先进环,过一会,slow也进环,此时开始追击。假设此时fast与slow之间的距离为N,那么每追击1次,fast与slow的距离就会缩小2步
那么追击过程中的距离变化就会是这样
从这里就变得有意思起来了,这里的距离变化一定能变成0吗?
显然,这里就要分为N是奇数还是偶数两种情况来看待了
当N是偶数时,最后距离为0,表示fast==slow
而当N是奇数时,最后距离变为-1,这是什么意思呢?
这意味着fast超过了slow,假设环的长度为C,那么它们的距离就变成了C-1,接下来就要进行新一轮的追击
图示如下:
那么在新一轮的追击里 ,此时fast与slow之间的距离为C-1,因为每追击1次,fast与slow的距离就会缩小2步,所以这里也要分C-1是奇数还是偶数来看待
如果C-1是偶数,那么下一轮就追上了
但是:C-1是奇数的话,那么它在这一轮追击又会追不上,而且在下一轮追击里,由于二者的距离又是C-1,且C-1是奇数,那么导出的结论就是永远都追不上
这里博主总结了一张图片,方便小伙伴们梳理
到此为止,好像一切都没问题,事实上,博主看过其他的一些博客讲到这里也就结束了,
但是,其实如果对这个问题深究,我们其实会发现,这个永远追不上的分支的条件可以进一步的求证
下面我们再来重新审视一下这个永远追不上的条件:它满足:
1.N是奇数
2.C-1是奇数
如果这2个条件同时存在,那么,确实是永远追不上
但是,有没有一种可能,这2个条件是不能同时满足的呢?
假设从链表头到入口点的长度为L,其余与上面假设同
我们来算一下slow刚入环时,slow和fast各自走过的距离
slow走的距离:L
fast走的距离:L+x*C+C-N(x是fast转的圈数)
根据3倍slow的距离 = fast的距离可得:
3*L = L+x*C+C-N => 2*L = (x+1)*C-N
我们观察这个我们推出来的式子,左边一定是个偶数,如果满足N是奇数C-1是奇数,那么右边的等式就是偶数-奇数,显然这个 偶数 = 偶数-奇数 是不成立的!
所以这也就说明了这个永远追不上的2个条件也是不能同时成立的
好了,到此为止,上面提出的快慢指针的第二个问题slow走1步,fast走3步能够追上吗?也分析完毕,结果说明无论那个分支最后都是能够追上的
至于第三个问题,这里也就不展开了,通过2个问题的分析,其实我们已经能Get到这个问题考察到的一个逻辑的思维,而且4步,5步,6步的情况涉及的追击圈数,讨论情况也确实比较繁琐,所以就不细说了
下面我们来看一下 环形链表II
给定一个链表的头节点
head
,返回链表开始入环的第一个节点。 如果链表无环,则返回null
。如果链表中有某个节点,可以通过连续跟踪
next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。如果pos
是-1
,则在该链表中没有环
环形链表II 即上一道题目的升级版,要求我们返回链表开始入环的第一个节点
思路:
快慢指针,slow走一步,fast走两步
这里我们需要用slow与fast走过的距离来找到其中的关系
我们假设链表头到入口点的距离为L
入口点到相遇点的距离为X
环的长度是C
图示如下:
在计算距离之前,这里我们需要先思考一个问题,slow有没有可能转了超过1圈?
答案是不可能
理由很简单:因为如果slow走了一圈,那fast都走了两圈了,早就追上了
(假设fast追上slow时,fast转了n圈(n>=1))
所以slow走过的距离为L+X , fast走的距离是L+ n*C+X
根据2倍slow的距离 = fast的距离可得:
2*(L+X) = L+ n*C+X
=> L = n*C-X
用这个公式我们就能得到一个很巧妙的方法:因为L = n*C-X,我们就可以让一个指针从链表头开始走,另一个从相遇点开始走,它们最后会在环的第一个节点相遇,也就找到了我们想要的
所以用这个方法我们就能很轻易的做出这个环形链表II
代码如下:
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode *slow = head;
struct ListNode *fast = head;
while(fast && fast->next)
{
slow = slow ->next;
fast = fast->next->next;
if(slow==fast) //是环形链表
{
struct ListNode * hhead = head;//hhead是在链表头的指针
struct ListNode *meet = slow; //meet是在相遇点的指针
while(meet!=hhead)
{
meet = meet->next;
hhead = hhead->next;
}
return meet;//返回带环的第一个节点
}
}
return NULL;//不是环形链表
}
然后就过了:
所以说,正如前面所说,这里考察的更多的是一种逻辑,编程写代码反而是最简单的
我们用这个slow走一步,fast走两步的快慢指针解决了这个问题,
这里如果像前面一样分析走三步的就麻烦了,因为slow走的圈数可能超过一圈
所以也就不涉及了
好啦,到此为止,今天的环形链表小专题就结束啦,如果文中分析,题解代码有不足的地方欢迎大家在评论区讨论和指正
让我们在接下来的时间里一起学习,一起进步吧~