赞
踩
目录
二、如何证明fast和slow不会在回环中错过,永远都遇不上?
三、为什么slow走1步,fast走的是2步?能不能fast一次走3或者n步?
A:数据结构中的链表入门必学的一种线性结构,那单向链表带环是什么呢?
B:老师又来考我了,这不是送分题吗?单向链表中的一个节点的指针指向之前的节点,形成闭环就是链表带环。
A:那如何判断一个链表是否有环?
B:简单,用快慢指针。先定义两个指向该链表类型的指针,为了方便理解,一个叫fast,一个叫slow。让slow指针一次走1步,让fast指针一次走2步。通过判断fast是否为空,来决定循环是否继续。如此,只会存在两种情况。当fast不为空,只需要在每次行动后判断fast和slow指向的地址是否相同,就可以判断有没有带环。如果fast和slow指向地址相同,说明链表带环(因为只有存在回环,才能让同起点出发且速度更快的fast指针和slow指针相遇);当fast为空,说明该链表没有形成闭环,没有带环。
A:那如何证明fast和slow不会在回环中错过,永远都遇不上?
B:好问题,让我想想。。。。。。
B:为什么呢?我好像明白这样是可以的,但是要怎么证明?
A:那就让我来讲解为什么slow指针走一步,fast指针走两步在在回环中不会错过且一定可以遇上。
第一步:fast和slow指针从链表的第一个节点开始走,fast一次走两步,slow一次走一步。
第二步:fast速度是slow的一倍,如果链表不带环,fast肯定会先到链表末尾。如果链表带环,fast会比slow先进入回环。
第三步:slow在fast之后进回环,且一定经过会在入环点。当slow在入环点时,fast和slow会相差一段距离,假设距离为N步。
第四步:fast每次都会比slow多走一步。从相对运动的角度来看,slow对于fast来说每次都会更接近一步的距离。从slow入环时,fast和slow相距N步,到每一次循环距离都会减1。作为正整数的N肯定会被减到0,因此,fast肯定会与slow相遇且不会错过。
B:对对对,我就是怎么想的,就是说不上来。
A:那为什么slow走1步,fast走的是2步?能不能fast一次走3或者n步?(n为比3大的正整数)
B:老师我懂了。我认为如果fast不是2步,会出问题。
第一步:fast和slow指针从链表的第一个节点开始走,fast一次走3步,slow一次走1步。
第二步:fast速度比slow快。如果链表不带环,fast肯定会先到链表末尾。如果链表带环,fast会比slow先进入回环。
第三步:slow在fast之后进回环,且一定经过会在入环点。当slow在入环点时,fast和slow会相差一段距离,假设距离为N步。
第四步:fast每次都会比slow多走2步。从相对运动的角度来看,slow对于fast来说每次距离都会减少2步。但是,当fast快要接近slow时会出现两种情况。第一种是fast和slow距离为0,两者相遇。第二种是fast和slow距离差1,当fast下一次行动时就会和slow错过,fast和slow的距离就是K-1。(K为链表回环的节点个数)如果K为偶数,K-1就是奇数。说明fast和slow距离相差次数不可能被2减为0。因此fast每次都会和slow错过。如果K为奇数,K-1就是偶数。那么fast和slow的距离是可以被2减为0的,fast会和slow相遇。
下面总结fast走3步,slow走1步有两种情况会遇上:(1)当slow指针进入圆环时,fast和slow相距距离为偶数(2)链表回环中的节点个数为奇数
第一步:fast和slow指针从链表的第一个节点开始走,fast一次走4步,slow一次走1步。
第二步:fast速度比slow快。如果链表不带环,fast肯定会先到链表末尾。如果链表带环,fast会比slow先进入回环。
第三步:slow在fast之后进回环,且一定经过会在入环点。当slow在入环点时,fast和slow会相差一段距离,假设距离为N步。
第四步:fast每次都会比slow多走3步。从相对运动的角度来看,slow对于fast来说每次距离都会减少3步。当fast快要接近slow时会出现下面这种情况。
当fast和slow距离差1,当fast下一次行动时就会和slow错过,fast和slow的距离就是K-1。(K为链表回环的节点个数)当fast第二次接近slow时,他们之间的距离会差2,当fast下一次行动时就会和slow错过,fast和slow的距离就是K-2。当fast第三次接近slow时,他们之间的距离会差3,当fast下一次行动时就会和slow相遇,fast和slow的距离就是0。
可以看出,fast走4步,slow走1步会出现每3次fast靠近slow,只有1次相遇,其他两次都错过。
当slow走1步,fast得走n步。n为偶数,fast和slow一定相遇。n为奇数,fast和slow可能会相遇。n为3到3以上的步数一定会存在fast与slow错过的情况,且偶数的n越大,在fast接近slow的次数相同时,错过的概率就越大。n为奇数视情况而定,主要分析slow在入环点时,fast和slow的距离N,和fast与slow第一次错过的距离K。
根据先前分析,我们知道了fast指针走2步,slow指针走1步一定会在回环中相遇。由此当fast和slow第一次在回环中相遇时,我们可以得到以下信息,为了方便理解,我们通过图的方式,展现各个数值的具体意义。
fast和slow在回环中第一次相遇时,fast在回环中走过n圈(n最小为1),slow不可能在回环中走过1圈(不明白可以看上一篇文章)。因此,假设slow从回环入口节点处走C步时,便会与fast相遇。可以得到slow走了X+C步,fast走了X+C+nK步(K表示回环一圈的步数)。由于fast走的步数是slow的一倍,所以2(X+C) = X+C+nK。
简化式子:(X+C) = nK
我们需要求得是回环入口节点的位置,所以需要得到的是X等于什么?
根据需求,我们可以将式子转换为:X = nK-C
上式中可以得到从链表头走到回环入口节点需要从相遇点走n圈减C的路程(n圈减C的路程也就是在相遇点位置走到回环入口的步数加n-1圈的步数)。
简而言之,只需要在fast和slow第一次相遇时,记录相遇点的位置。从相遇点走X步就会到达回环入口节点,X步数是链表头到相遇点的距离。两者走相同步数到达的同一地点,就是相遇点的位置。
需要动手实践的小伙伴可以点后面的链接进入力扣的环形链表II(力扣)
下面是验证代码和力扣刷题图片:
- /**
- * Definition for singly-linked list.
- * struct ListNode {
- * int val;
- * struct ListNode *next;
- * };
- */
- struct ListNode *detectCycle(struct ListNode *head) {
- struct ListNode *fast = head;
- struct ListNode *slow = head;
- while(fast && fast->next)
- {
- fast = fast->next->next;
- slow = slow->next;
- if(fast == slow)
- {
- struct ListNode *meet = fast;
- struct ListNode *ret = head;
- while(meet != ret)
- {
- meet = meet->next;
- ret = ret->next;
- }
- return meet;
- }
- }
- return NULL;
- }
如有不当之处,感谢各位大佬指正。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。