浅谈双指针技巧（二）---通过双指针判断链表成环问题

在上一篇文章（https://www.cnblogs.com/jilodream/p/16666435.html）中，我们已经知道可以通过快慢指针，最终判断一个单向链表是否成环。
一般在判断存在环之后，还有一个经典的问题：
查找环的起点节点是哪里呢
力扣 142. 环形链表 II （https://leetcode.cn/problems/linked-list-cycle-ii/）
也就是查找到下图中的这个位置

乍一看这个问题很难处理，除非像前文说的通过缓存来判断首次加入到缓存中的节点外，并没有什么其他好的办法。

如果直觉不能给我答案，我们往往采用数学的办法：

 

如上图，假设判断有环后，慢指针执行的距离是N，则快指针的执行的距离是2N。他们相遇的点是meet点。我们可以理解2N-N，也就是快指针超过慢指针的距离，其实就是围绕meet节点绕了x圈（x>=0）。
所以最终的结论就是：(防盗连接：本文首发自http://www.cnblogs.com/jilodream/ )

N=慢指针走的距离=快指针超过慢指针的距离=围绕meet节点走x圈

此时我们让两个指针（a、b）同时走上述的两个N，也就是一个从head节点，一个从meet节点开始，同速，一直走N步，最终会同时到达meet节点。
而这个过程的最后一部分，也就是start节点到meet节点，两者的路径其实是重合的。因此这两个指针（a、b）会首先在start节点相遇，然后同时走相同的一段路径，并最终一同走到meet节点。
如下图：

a指针移动距离=b指针移动距离=N-lastLen（lastLen表示从start节点到meet节点之间的最短距离+x*环的周长）

也就是：
a指针移动距离=b指针移动距离
所以我们在寻找环的起点start节点时，分为两部分：
1、通过快慢指针找到二者的相遇点meet节点。(防盗连接：本文首发自http://www.cnblogs.com/jilodream/ )
2、新定义两个节点a、b，分别指向meet 节点和head节点。两者按照相同的速度前进，第一次相遇的节点就是环的起始节点start

我们直接看代码：

 

    public ListNode detectCycle(ListNode head) {
        ListNode tempHead = head;
        if (tempHead == null) {
            return null;
        }
        ListNode low = tempHead;
        ListNode fast = tempHead;
        while (true) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            fast = fast.next.next;
            low = low.next;
            if (fast == low) {
                break;
            }
        }
        ListNode a = tempHead;
        ListNode b = fast;
        while (true) {
            if (a == b) {
                break;
            }
            a = a.next;
            b = b.next;
        }
        return a;
    }