解决思路

想法

当然一个跑得快的人和一个跑得慢的人在一个圆形的赛道上赛跑，会发生什么？在某一个时刻，跑得快的人一定会从后面赶上跑得慢的人。

算法

Floyd 的算法被划分成两个不同的 阶段 。在第一阶段，找出列表中是否有环，如果没有环，可以直接返回 null 并退出。否则，用 相遇节点 来找到环的入口。

阶段 1

这里我们初始化两个指针 - 快指针和慢指针。我们每次移动慢指针一步、快指针两步，直到快指针无法继续往前移动。如果在某次移动后，快慢指针指向了同一个节点，我们就返回它。否则，我们继续，直到 while 循环终止且没有返回任何节点，这种情况说明没有成环，我们返回 null 。

下图说明了这个算法的工作方式：

public class Solution {
    //
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        //前两个节点目的是判断是否有环
        ListNode first = head;
        ListNode second = head;
        //当有环的时候，第一个节点和result_node节点同时往后走，相遇的时候即为环节点
        ListNode result_node = head;
        while (first!=null && second!=null && first.next!=null){
            first = first.next.next;
            second = second.next;
            if(first==second){
                while(first != result_node){
                    first = first.next;
                    result_node = result_node.next;
                }
                return result_node;
            }
        }
        return null;
    }
}