环形链表OJ

来自力扣的一道oj题：142. 环形链表 II - 力扣（LeetCode）

题目描述：

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定

链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。

如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的

实际情况。

例题展示：

示例1：

 

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例2：

 

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

 问题分析：

相信大家如果是初次做这道题一定会有些懵逼，其实大家最多想到的解法就是链表相交，这种方法

是可行的，但大家一定都做过相交链表相关的题目，代码相对来说比较多，而且这道题会比相交链

表写的更多，因为我们还需要先找到相应的相遇点，并断开下一个节点，再通过相遇点来分出两个

链表，才可以找到链表的交点，所以会变的更加繁琐。

那么有没有一种又快速又简单的方法呢，大家都知道，越简单的方法对应着越复杂的思想，所以接

下来我们要进行推导一个结论，我可以先将这个结论告诉大家，让后在证明完成后你们便会恍然大

悟！

 结论：一个指针从相遇点走，一个指针从起始点走，并且走的步幅相同，他们最后会在入环点相

遇。

证明方法：

要想又更好的证明思路就需要画图：

上面是一副典型的环形链表的图，我分别标出了相关元素，有助于我们理解。

首先我们需要先定义slow,fast两个指针，fast一次走两步，slow一次走一步，对应到上面的图，假

设他们都是从起始点出发，那么他们到相遇点的情形，应该是

slow:从起始点出发，经过了入环点，到达了相遇点，与fast相遇。

fast:从起始点出发，到达了相遇点之后，开始走环形一圈，直到下一次到达相遇点，与slow相遇。

对应的可以得到走过的路程的算术表达式：

slow:L+X

fast:L+C+X

又因为有等量关系，fast走的路程是slow的二倍：

2*(L+X) = L+C+X

化解得：

L = C-X

此时我们的结论就显而易见了。但是，我在给大家画一张图，来看看我们得到的结论到底正不正

确： 

 当周长c远远小于L的时候，我们上面的公式还正确吗？

显然是错误的，因为fast在里面可能不止转一圈，这是大家最容易犯的错误。

对这种情况我们重新推导：

设他们都是从起始点出发，那么他们到相遇点的情形，应该是

slow:从起始点出发，经过了入环点，到达了相遇点，与fast相遇。

fast:从起始点出发，到达了相遇点之后，开始走环形N圈，直到下一次到达相遇点，与slow相遇。

对应的可以得到走过的路程的算术表达式：

slow:L+X

fast:L+N*C+X

又因为有等量关系，fast走的路程是slow的二倍：

2*(L+X) = L+N*C+X

化解得：

L = N*C-X

 这次证明才是最正确，最科学的，这个公式才能得到我们的结论：

结论：一个指针从相遇点走，一个指针从起始点走，并且走的步幅相同，他们最后会在入环点相

遇。

代码解决：

只要会了这种思想，代码是不成问题的

代码展示：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast,*slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
 
        if(slow == fast)
        {
            struct ListNode *meet = slow;
            struct ListNode *start = head;
            while(meet!=start)
            {
                meet = meet->next;
                start = start->next;
            }
 
            return meet; 
        }
    }
    return NULL;
}

从这道题可以看出来学习语言的时候也需要一些数学基础的，但是也不需要太多，大家也不要因此

而产生压力，实在不行的话其实相交链表也是一个很好的选择！！