C语言之带环链表

带环链表是数据结构链表中的一个经典问题，这里我们研究该问题分为两个方向：链表是否带环、返回链表的入环节点。

下面我们通过两个题目来分析带环链表：

1.判断链表是否带环

141. 环形链表 - 力扣（LeetCode）

 那么我们要怎么判断一个链表是否带环呢？

这里我们直接给出答案：借助快慢指针来判断链表是否带环。

我们创建两个指针变量slow和fast，slow一次走一步，fast一次走两步，如果链表带环，那么fast就会先进入环，当slow也进入环之后，它们就开始了追击，因为fast走得比slow快，所以fast和slow一定会相遇，如果fast和slow相遇了，就证明了该链表是带环链表；如果fast走到了NULL，那么就说明该链表是不带环的。

分析图如下：

 这个逻辑还是很简单的，该操作的代码也很简单，这里直接给出：

bool hasCycle(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)
        {
            return true;
        }
    }
    return false;    
}

到这里了就有问题了，那这样子写的原理是什么呢？我们借助图来解释一下：

到这里，问题就解决了么？其实还没有，fast走2步可以，那么fast走3步，4步，n步可不可以呢？ 

下面我们来研究一下fast走3步的情况：

1.1fast走3步

我们借助图来分析：

我们看到，如果C-1是奇数的话，他就会陷入循环中，每一次都追不上，且每一次的距离都是C-1。那么fast走4步和走n步都是同样的分析道理，大家感兴趣的话可以自己推一下。 

我们现在就要问了，fast走三步真的追不上么？

1.2fast走三步到底追不追得上？

我们在上面说当N是奇数且C-1是奇数的时候就追不上，那么事实是这样的么？我们继续分析一下。我们假设进环前的路程为L，所以slow走的路程就是L，fast走的路程是L+x*C+N。x表示fast在环中走的圈数，因为在slow进环之前，fast可能已经在环中走了好几圈了。N表示slow刚入环时，fast和slow的距离。

然后又因为fast一次走三步，slow一次走一步，所以fast走的路程是slow路程的三倍。所以有等式：3L = L+x*C+N。化简得：2L = x*C+N。

综上所述，当fast一次走三步时，不管slow刚进入环时，fast和slow的距离N是奇数还是偶数，都会追上。偶数会在第一次追击就追上；奇数则会在第二次追击追上。 

2.返回带环链表的第一个入环节点 

142. 环形链表 II - 力扣（LeetCode）

我们在先前判断了一个链表是否带环，我们现在要返回该带环链表的入环节点。 

如上图所示，我们要返回的入环节点就是节点2。 

其实非常的简单，我们现在已经知道，不管fast一次走多少步，fast和slow总会相遇。我们定义连个指针head和meet，分别从链表的第一个节点和fast、slow相遇的节点开始遍历，等到head和meet相等的时候，此时两个指针指向的就是环入口的节点。

这是什么原理呢？

fast和slow的路程为什么是这样的呢？

我们想，slow可不可能在环中走过超过一圈呢？当然不可能了。因为fast走的是slow的2倍，如果slow走了一圈，那么fast就走了两圈，它们肯定就已经相遇了。所以slow的路程是L+N。

而因为fast走得比较快，所以当slow入环时，fast已经在环中转了好几圈了。那么我们想一下，fast可不可能一圈都没转完？不可能，因为如果一圈都没走完，那么fast走的路程还没有slow的多，因为slow路程的2倍才是fast的路程。

所以根据上面的公式，以及fast一次走二步，slow一次走一步，我们可以得出一个等式：

2（L+N）= L+x*C+N。化简得：L+N = x*C ，继续化简得：L = x*C-N，我们将该式带入图中：

 其上，就是我的证明过程。head和meet同时遍历链表，当相等的时候，它们指向的都是入环的第一个节点。下面给出代码：

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)
        {
            while(head != fast)
            {
                head = head->next;
                fast = fast->next;
            }
            return head;
        }
    }
    return NULL;
}