环形链表的求解方式有两种：

• 第一、通过记录每个引用来判断是否有重复引用的方式来判断是否存在环，如果直到链表遍历结束都没有重复引用出现，那就是不存在环，否则就是存在环
• 第二、通过快慢指针来判断是否存在环。因为链表存在环的问题，所以慢指针肯定会追上快指针。
  第一种解法需要额外的存储空间，时间效率更高，而第二种解法不需要额外的存储空间，时间效率稍微次于第一种解法。
  下面主要介绍快慢指针的方式来求解环形链表的问题。
  我认为这道题的问题主要是数学问题，而不是编程问题。

首先看结论：

快慢指针同时从头结点出发，慢指针每次移动一个单位，快指针每次移动两个单位，当快慢指针相遇的时候，让一个新的结点newNode从头结点出发，然后newNode结点和slow指针每次移动一个单位，newNode和slow指针相遇的即为环的入口位置。

证明如下：

133abe248ca584f175629bcdce7c561.png

为什么newNode和slow指针相遇的即为环的入口位置？

fast指针走的路程为：a+b+n(b+c)
slow指针都的路程为：a+b
因为fast指针速度为slow指针速度两倍，所以a+b+n(b+c)=2(a+b) => a = (n-1)(b+c)+c

为什么slow指针走的路程为 a+b？

假设环的长度为n，快慢指针相遇的时候 fast指针所在的位置为x，所以此时fast指针与slow指针的距离为 n-x，所以fast指针追上slow指针需要 n-x 步，而 n > x >= 0，所以快慢指针只会在第一圈相遇。
极限情况 x = 0，即是快慢指针在入口处相遇，此时就是 a = xn,即a的长度是环的长度的整数倍。

//代码奉上
public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        while(fast != null){
            slow = slow.next;

            if(fast.next != null){
                fast = fast.next.next;
            }else {
                //说明不存在环
                return null;
            }

            //当快慢指针相遇，这是从头结点出发的指针会刚好在环入口点和慢指针相遇
            if(slow == fast){
                ListNode ptr = head;
                while(slow != ptr){
                    slow = slow.next;
                    ptr = ptr.next;
                }
                return slow;
            }
        }

        //不存在环
        return null;
    }

参考leetcode142