链表环的问题：操场上，如何多次偶遇女神？

作者|莱乌

一个风清月皎的夜晚，小莱独自在操场漫步。突然一个熟悉的身影从旁边经过，小莱定睛一看，这不是心怡很久的女神吗？小莱快走几步追上女神后打了个招呼就径直往前走了（没出息）。为了加深女神对自己的印象，小莱决定再来一次偶遇（回头是不可能回头的）。只见小莱加快了步伐，终于再次偶遇到了自己的女神.....

本期主要分为以下几个部分：

• 判断是否有环

• 环的长度
  

• 环的入口
  

• 链表长度

画外音：关于单链表知识，请点击回顾。

如图，这是一个链表存在环的示意图。

我们如何来判断是否有环呢？小莱偶遇女神的例子或许对我们有所启发。

在A点小莱和女神第一次相遇（起点）。

为了再次相遇，小莱在女神保持速度不变的情况下，采取了加(风)快(驰)步(电)伐(掣)的策略。由于操场是个环形，那么在两个人一快一慢的场景下必然会再次相遇，于是在B点小莱又遇到了自己的女神。

画外音：操场上想尽快遇到妹子，横穿草坪超近道也是可以的哈！

那么结合到链表里如何处理呢？接下来我们的主角就该登场了：

在链表环的问题中我们常常用快慢指针来进行处理，即设置slow、fast两个指针变量（slow可以看作女神，fast可以看作小莱）：

• slow每次走一步，即slow->next；

• fast每次走两步，即fast->next->next；

如果slow和fast相遇的话，即可以判断当前链表中有环。

代码实现：

while(slow!=NULL && fast->next!=NULL) {
    slow = slow->next;
    fast = fast->next->next ;
    if (slow == fast) {
        return true;

 }

既然知道了链表中有环，那么如何计算这个环的长度呢？

小莱和女神在B点相遇了，那么女神按照小莱的轨迹走一遍再回到B点，行走的路程不就是环的长度吗？

画外音：真他娘的聪明。

代码实现：

while(slow!=NULL&&fast->next!=NULL){
       slow = slow->next;
       fast = fast->next->next ;
       if (slow == fast) {
           break;
       }
   }

   for(p=slow->next;slow!=p;p=p->next){

len++;
}

p节点用来记录B点的位置。

如图所示，现在我们想要知道环的入口位置。

假设 A到C的距离为x，C到B的距离为y，环的长度为r。在B点相遇时，女神走的距离为s，那么小莱的距离则为2s（速度是女神的2倍）。

那么可以根据：

推导出：

画外音：n表示相遇时快指针（小莱）比慢指针（女神）多走的环数。

根据这个公式，我们可以设置两个指针，一个在相遇点B，一个在起点A，然后两个指针同时走（每次走一步），当这两个指针相遇时，此时的位置即为环的入口点。

while(slow!=NULL&&fast->next!=NULL){
       slow = slow->next;
       fast = fast->next->next ;
       if (slow == fast) {
           break;
       }
   }

   p = list->head;

s = slow;

while (p != s) {

    p = p->next;

    s = s->next;

}

进行到这里，链表长度的问题就简单的多了。

根据前面两步，我们知道了环的长度r，同时在获取环的入口时可以计算出起始点到入口的距离x。那么链表的长度L就很容易得出来了。

链表长度L =  起始点到入口的长度x + 环的长度y

文章整体目录

如何获取

很简单，在我的微信公众号 帅地玩编程 回复 程序员内功修炼 即可获取《程序员内功修炼》第一版和第二版的 PDF。

推荐，推荐一个 GitHub，这个 GitHub 整理了几百本常用技术PDF，绝大部分核心地技术书籍都可以在这里找到，GitHub地址：https://github.com/iamshuaidi/CS-Book（电脑打开体验更好），地址阅读原文直达