当前位置:   article > 正文

数据结构-链表带环问题_链表有环

链表有环

目录

一、如何判断一个链表是否有环?

二、如何证明fast和slow不会在回环中错过,永远都遇不上?

三、为什么slow走1步,fast走的是2步?能不能fast一次走3或者n步?

(1)fast走3步,slow走1步的情况。

(2)fast走4步,slow走1步的情况。

总结:

四、如何求链表回环的入口节点

刷题:


一、如何判断一个链表是否有环

A:数据结构中的链表入门必学的一种线性结构,那单向链表带环是什么呢?

B:老师又来考我了,这不是送分题吗?单向链表中的一个节点的指针指向之前的节点,形成闭环就是链表带环。

A:那如何判断一个链表是否有环

B:简单,用快慢指针。先定义两个指向该链表类型的指针,为了方便理解,一个叫fast,一个叫slow。让slow指针一次走1步,让fast指针一次走2步。通过判断fast是否为空,来决定循环是否继续。如此,只会存在两种情况。当fast不为空,只需要在每次行动后判断fast和slow指向的地址是否相同,就可以判断有没有带环。如果fast和slow指向地址相同,说明链表带环(因为只有存在回环,才能让同起点出发且速度更快的fast指针和slow指针相遇);当fast为空,说明该链表没有形成闭环,没有带环。

二、如何证明fast和slow不会在回环中错过,永远都遇不上?

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:对对对,我就是怎么想的,就是说不上来。

三、为什么slow走1步,fast走的是2步?能不能fast一次走3或者n步?

A:那为什么slow走1步,fast走的是2步?能不能fast一次走3或者n步?(n为比3大的正整数)

B:老师我懂了。我认为如果fast不是2步,会出问题。

(1)fast走3步,slow走1步的情况。

第一步: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)链表回环中的节点个数为奇数

(2)fast走4步,slow走1步的情况。

第一步: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(力扣

下面是验证代码和力扣刷题图片:

  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. * int val;
  5. * struct ListNode *next;
  6. * };
  7. */
  8. struct ListNode *detectCycle(struct ListNode *head) {
  9. struct ListNode *fast = head;
  10. struct ListNode *slow = head;
  11. while(fast && fast->next)
  12. {
  13. fast = fast->next->next;
  14. slow = slow->next;
  15. if(fast == slow)
  16. {
  17. struct ListNode *meet = fast;
  18. struct ListNode *ret = head;
  19. while(meet != ret)
  20. {
  21. meet = meet->next;
  22. ret = ret->next;
  23. }
  24. return meet;
  25. }
  26. }
  27. return NULL;
  28. }

 如有不当之处,感谢各位大佬指正。

本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/426471?site
推荐阅读
相关标签
  

闽ICP备14008679号