java - 142. 环形链表 II - 通俗易懂题解

 1、 首先设置快慢指针，慢指针走一步，快指针走两步
 2、 两者如果相遇说明有环，假设慢指针走了k步，则快指针走了2k步。
    慢指针从头走到相遇点为k，那么从相遇点再走k步就会再次走到相遇点，也就是快指针的2k步。
    假设环起点距离相遇点为m步，那么慢指针从头走到环起点为k-m步，因为走到环起点再走m就走到了相遇点。
    如果慢指针走到相遇点，再走k步将会第二次到达相遇点（因为共2k步，和快指针路径一致）。所以，如果走的不是k，而是k-m也会到达环起点。
 3、 2中分析了2种走到环起点的办法，都是走k-m步，一种是从起点走，一种是从相遇点走。那么在快慢指针第一次相遇之后。
    令一个指针从头开始，另一个从相遇点开始，两者步伐一致，第一次相遇就是走了k-m步，就是起点。

public class Solution {
    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        // 1 寻找相遇点
        ListNode fast = head,slow = head;
        while (fast != null && fast.next != null) { // 走到null说明没有环
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) break; // 没走到null会一致走到相等，说明有环
        }
        if (fast == null || fast.next == null)  return null;  // 没有环
        if (slow == fast) slow = head; // 有环


        // 2 寻找起点：第一次相遇就是起点
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}