题目概述(中等难度)

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：

不允许修改给定的链表。

进阶：

你能用 空间复杂度O(1)解决此问题吗？

示例 1：

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

示例 2：

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

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

附上leetcode链接：

点击此处进入leetcode

思路与代码

思路展现

这道题目是环形链表Ⅰ的一个变型，那个题目是为了让我们判断一个链表中是否有环，这个题目是为了让我们找到入环的第一个节点.

这道题目同样运用的是我们的经典思路快慢指针以及推导公式的思想

思路是这样的：

1：首先定义快指针fast和慢指针slow分别指向我们的头节点

2：fast指针一次走两步，slow指针一次都一步，如果链表有环，那么slow指针和fast指针按照这样的走法终会相遇.如下图所示:

设从头节点到作为环入口点的节点的距离为X

设从入口点到相遇点的距离为L

设整个链表环的长度为C

因为fast指针的速度永远都是slow指针速度的二倍，所以最终如果fast指针与slow指针在相遇点相遇的话，fast指针所走过的路程是slow指针所走过的路程的2倍

通过分析，我们可以知道：

fast指针所走过的路程为X+NC+L(N代表所有的环的圈数)

slow指针所走过的路程为X+L

因为fast指针所走过的路程是slow指针所走过的路程的2倍，所以由此我们可以得出一个等式：X+NC+L=2(X+L)==>NC=X+L

所以X=NC-L,当N=1时，X=C-L，从这里我们可以知道从相遇点到环的入口节点的距离就等于从头节点到作为环入口点的节点的距离X

很多同学此时就会纳闷了，为什么只考虑N=1的情况?明明N代表圈数，N越大，NC就越大，那么从相遇点到环的入口节点的距离怎么可能等于从头节点到作为环入口点的节点的距离X呢？

答案当然是不管我们的fast指针在这个环里饶了多少圈，fast指针的最后一圈直到两个指针相遇的这种情况其实就等价于fast指针只走一圈后两个指针相遇的情况.

3:知道了怎么走的之后，我们此时先让fast指针和slow指针相遇，相遇后，让slow指针回到头节点的位置，fast指针此时还在相遇点，根据前面的推导我们知道，相遇点到入环第一个节点的位置就等于从头节点到入环第一个节点的位置,所以此时当fast和slow还没有遇见前，fast指针和slow指针开始往下遍历，每次只走一步，此时当fast和slow指针再次相遇的时候，fast和slow指针同时指向的节点即为我们入环的第一个节点.

4:同时当找到相遇点，slow指针指向头节点前，还要对链表是否存在环在进行下判断，如果节点个数为偶数的链表和节点个数为奇数的链表不存在环，就返回null.

代码示例

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        //开始寻找相遇点
        while(fast!=null&&fast.next!=null){
        //fast指针走两步，slow指针走一步
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
              //找到相遇点后跳出循环
                break;
            }
        }
        //如果不存在环，返回null
        if(fast==null||fast.next==null){
            return null;
        }
        //让slow指针重新指回头节点,fast指针此时在相遇点
        slow=head;
        //开始寻找入环的第一个节点
        while(fast!=slow){
        //fast指针和slow指针各走一步
            slow=slow.next;
            fast=fast.next;
        }
        return fast;
    }
}

总结

1:此算法

时间复杂度O(N)

空间复杂度O(1)

2:对于快慢指针这种题目还需要好好斟酌，前面我们也有用到快慢指针的思路，希望大家好好复习,同时这道变形题目还带有一定的数学思想在里面，需要大家推导公式,也具有一定的小技巧在里面.