环形链表2

题目 环形链表2

image-b1fc20a2

思路分析

image-a9d9fc30

由上一题可以得知若存在环就一定会相遇

那么假定相遇的位置为c点

入口点为b点 我要想办法找到这个b点

那么 让slow指针往回退到b点 也就是退y个距离 那么fast在那个时间点就应该在c-2y的地方（退2y个距离）

image-1bf31568

也就是说 在slow走了x长度的时候 fast（2倍速的slow）走到了d这个点 走了两倍的x长度

那去掉重复的ab那一段 多出来的不也就是x长吗

也就是说 x长度可以绕这个环n圈后 到了3/4位置处j

（只是对于当前图d点的解释 示例在3/4处好理解 其实是以d→b = b→c = y来判断的）

image-3e15add6

那么也就是说 我x可以绕这个环走n圈多3/4圈 至于n是多少无所谓

而c点是在1/4处的 是不是可以刚好和那3/4补满一圈？

（真实情况是 c在入口y处 x能绕圈走n圈差y到下一圈）

那么意思就是 我从c处 再走一个x 就一定能到b点咯

所以当相遇时 可以把其中任意一个指针回到起点

再把两个指针以同样的速度去走

那个指针下一次相遇时

就是我们的环的入口

代码实现

 class Solution {

 public:

  ListNode* detectCycle(ListNode* head) {

    ListNode* slow = head;

    ListNode* fast = head;

    while (fast && fast->next) {

      slow = slow->next;

      fast = fast->next->next;

      if (slow == fast) {

        slow = head;

        while (slow != fast) {

          slow = slow->next;

          fast = fast->next;

        }

        return slow;

      }

    }

    return nullptr;

  }

};

同类题型

视频讲解

⬅️ 环形链表 🏠 00-刷题理模型 ➡️ k倍区间