单向链表-有环链表环节点

今天学习的算法是链表有环判断的升级版，若链表有环则需返回环节点。

题目介绍

题目就不再进行介绍了，直接使用之前的图吧：

链表有环-题目.png

实现思路

获取换节点分为两步来实现，先看两步的图吧。
第一步：获取快慢指针相遇节点，直接使用链表有环判断的图吧：

链表有环-解题.png

第二步：获取环节点：

链表有环-环节点.png

难点说明

首先第一步目的是为了快慢指针的相遇节点，至于如何使用快慢指针来找到相遇节点就不再阐述了，可以参考单向链表-链表有环判断

下面重点来分析下第二步，为什么快慢指针相遇后，测量指针为什么和慢指针会在环节点相遇。回到快慢节点相遇时，假设快指针移动的步数为F（每次2步），慢指针移动的步数为S（每次一步），环的长度为b。因此我们可以得到以下两个公式：
1.F=2S；
2.F=S+nb，这个稍微难理解，可以想象下，快指针能和慢指针相遇，那快指针一定是基于相遇节点然后在环里面转了n圈。

根据上面的两个公式我们可以得到：S=nb；
假设从头节点到环节点的长度为a，环节点到相遇节点为x，则S=a+x；

再结合上面两个公式可以得到 a = nb-x。
那么只要让慢指针从相遇节点开始移动，移动nb-x后就会停留在环节点。
同时新增测量指针与慢指针同时开始移动，移动a步后停留在了环节的。
而a=nb-x，因此我们可以证明测量指针和慢指针一定会在环节点相遇。

实现代码

public ListNode detectCycle(ListNode head) {
    if (null == head || null == head.next) {
        return null;
    }

    ListNode slowNode = head;
    ListNode fastNode = head;
    while (null != fastNode && null != fastNode.next) {
        slowNode = slowNode.next;
        fastNode = fastNode.next.next;
        if (null != fastNode && slowNode == fastNode) {
        break;
        }
    }
    if (null == fastNode || null == fastNode.next) {
        return null;
    }

    ListNode surveyNode = head;
    while (surveyNode != slowNode) {
        surveyNode = surveyNode.next;
        slowNode = slowNode.next;
    }
    return surveyNode;
}