龟兔赛跑算法-力扣环形链表题目

本文主要是介绍龟兔赛跑算法-力扣环形链表题目，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目要求

环形链表1
问题1：
给你一个链表的头节点 head ，判断链表中是否有环。

环形链表2
给定一个链表，不仅需要判断链表中是否有环，，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
问题2在问题1的基础上，首先我们先来解决问题1.

题目1分析-求是否包含环

龟兔赛跑算法(Floyd’s Tortoise and Hare/Circle Detection)用于判断链表是否有环。具体的思路如下：
给定两个指针，一个快指针，一个慢指针，快指针一次走两步，慢指针一次走一步，在链表不存在环的情况下，快指针会达到最后的空结点，两者不会相遇。

而当链表中存在环的时候，快指针会提前进入环，而后在环内的某个结点处会和慢指针重合。

那么为什么快指针和慢指针一定会重合呢？
我们可以思考这样的一个情境，A和B同时在操场中跑步，其中A的速度是B的2倍，那么一开始A会超过B，之后：因为A的速度大于B的速度，那么在某一个时刻：A一定会和B再度相遇，再度超过B。但是要如何用数学公式证明呢，具体的证明可以参考这篇文章，写的很详细：证明过程

我是这么理解的：
如下所示：每次指针向前移动之后，快指针和慢指针之间的距离就会增加1。进入环中，一旦快指针超过慢指针之后，快指针在追赶慢指针的过程中，它们之间的距离每次都会缩短1个单位。而因为慢指针每次是向前移动1个单位的，因此，快指针在向前移动的过程中，一定会和慢指针在某个时间点重合。

所以问题就变得简单起来了：只要在两个指针向后移动的过程中，每次判断两者所指向的结点地址是否相同就可以。

代码如下：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast!=nullptr && fast->next!=nullptr)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow ==fast)
                return true;
        }
        return false;
    }
};

题目2分析-求入环结点

那么要如何找到入环的结点呢？这里涉及到简单的数学推导，主要参考的这篇文章：如何确定环的起点

假设：从头结点到入环结点之间的距离为m,从入环结点到两个指针重合的点之间的距离为n。环的长度为s，慢指针的步数为i步，快指针的步数为2i步。
(1).当快指针和慢指针相遇的时候有以下两个公式:
2 i = m + n + a ∗ s 2i=m+n+a * s 2i=m+n+a∗s i = m + n + b ∗ s i=m+n+b * s i=m+n+b∗s
a和b分别代表的是快指针跑的圈数和慢指针跑的圈数。
两式相减可以得到：
i=(b-a)*s
经过简单的推导可以发现：两者相遇的时候：慢指针所走的步数是等于环长度的整数倍。
快指针和慢指针相遇的时候：多走的部分恰好是绿色笔划出来的部分，即是环的长度的整数倍

(2)此时，让指针从链表的头部，一直向前走到环的入口结点处并统计步数k，那么步数k=m+i.这里的i是环的长度的整数倍，因为不管绕几圈，都会来到入口结点处。

(3)此时慢指针已经走了i步了(两者相遇的时候)，那么只需要慢指针向前走m步，就可以走到入口结点处。那么问题就转换为如何求m的取值。

此时令快指针指向链表的头结点处，快指针每次走1步,那么快指针和慢指针同时走m步后，两个指针会重合，故该指针指向的结点即为入口结点处。
代码如下:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
       //快慢指针的方法
       ListNode* fast=head;
       ListNode* slow=head;
    //    fast->next为空的话，下面的fast->next将有可能出现程序崩溃的现象。
       while(fast!=nullptr && fast->next!=nullptr)
       {
           fast=fast->next->next;
           slow=slow->next;
        //    代表有环
           if(fast ==slow)
           {
            //    fast指向头结点,fast向前移动m个点之后就会和slow在环的起点处重逢。
               fast=head;
               while(fast!=slow)
               {
                   slow=slow->next;
                   fast=fast->next;
               }
               //两者相等的时候：代表走到入环处
               return fast;

           }
       }
       return nullptr;
    }
};

拓展分析：如何求环的长度?

思路也很简单：快指针和慢指针相遇之后，快指针保持不动，慢指针向前移动。直到两者再次相等的时候，就可以计算出环的长度。

int cyclelength(ListNode* head)
{
	ListNode* fast=head;
    ListNode* slow=head;
    while(fast!=nullptr && fast->next!=nullptr)
       {
           fast=fast->next->next;
           slow=slow->next;
           //代表有环
           if(fast ==slow)
           {
           	   //初始化令i=1,即代表相交处的结点。
               int i=1;
               do
               {
                  slow=slow->next;
                  i++;
               }while(slow!=fast)
               return i;
           }
       }
       return 0;
    
}

这篇关于龟兔赛跑算法-力扣环形链表题目的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！